Breaks the array into two parts: sorted and unsorted. Finds the next best element from the unsorted section and puts it at the end of the sorted section.
1, 2, 3, 7, 4, 9
Here, 1, 2, 3 have been sorted already, so the algorithm will look through 7, 4, 9,find that 4 is the next best choice, and swap 7 and 4 to put the first 4 elements in the proper order.
Best case: O(n^2) Worst case: O(n^2) Average case: O(n^2)
Space complexity
In place
Worst case scenario
Selection sort performs the same on every kind of list
Insertion Sort
Best case: O(n) Worst case: O(n^2) Average case: O(n^2)
Space complexity
In place
Best case scenario: input list is in increasing order
Worst case scenario: input list is in decreasing order
It’s often used as the final stage of more sophisticated sorts, such as quicksort.
Works the best if the data is sorted or partly sorted.
Merge Sort
Splits the array in half, splits that half in half, and so on, until each element is on its own, then merges all the singular elements back together so one and one become two, two and two become four, and so on.
Best Case: O(nlogn). Worst Case: O(nlogn). Average Case: O(nlogn).
Space complexity
O(n)
Quick Sort
Picks a partition point and reorders elements so that values smaller than the pivot are to the left, and values larger are to the right. Pick new partitions for the left and right sides to sort further and further until a sorted array is generated.
Best Case: O(n logn) Worst case: O(n^2) Average case: O(nlogn)