Sorting Algos (short for Algorithms)

Bubble sort:

This algorithm goes through each array, swapping an item if the next one is smaller than the current item it's checking.

Optimisations:

• flag to let the algo know if any swaps were made in a pass, if no swaps were made, the list is sorted and the algorithm can halt
• keep track of where the "sorted" part of the list is so that you don't have to go through the entire list, only the unsorted bit

Insertion sort:

This time, instead of bubbling items to the top, we set the start of list to be "sorted", and slap in the rest of the items in order by comparing the items to the sorted part

Optimisations:

• Use an index to tell where the sorted part is rather than making a seperate array. This will save space in memory
• Use binary search to find out where to put the item in the sorted part of the list

Merge Sort:

Hella aura for this one, this is my fav guys.

- Split up the list into individual items.

- Merge those parts by comparing pairs of items to eachother to find out what order they should go in

- when comparing, if one of the items / mini arrays is empty, pop the other array onto the combined mini array and move on

- Slap these compared mini arrays into a seperate array, then compare those mini arrays and so on until it's all sorted

I don't really know how to describe this one too well, it's easier visually, but the best i can do is show a youtube video but i'm a lazy guy