Categorizing Sorting Algorithms

Stability: Stable sorting algorithms maintain the relative order of records with equal keys.

Algorithms

CAN BE STABLE, BUT BY DEFAULT IT’S NOT
Sorts an array by repeatedly finding the smallest element of the unosrted tail region and moving it to the front
The algorithm is not stable by default, but it’s possible to make it stable
One advantage of selection osrt is that it requires only O(n) write operations. If we have a system where write operations are extremly expensive and read operations are not, then selection sort could be ideal. One such scenario would be if we are sorting a file in-place on flash memory or an external hard drive.
It uses O(1) memory
Best/Average/Worst case = O(n^2)

STABLE
Given a list, take the current element and insert it at the appropriate position of the list, adjusting the list every time you insert.
It’s used either when the data is nearly sorted or when the problem size is small (because it has low overhead)
It uses O(1) memory
Best case = O(n); Worst/Average case = O(n ^2)

STABLE
Mergesort is an example of a divide-and-conquer algorithm that recursively splits the problem into branches, and later combines them to form the solution.
External sorting is a term for a class of sorting algorithms that can handle massive amounts of data. External sorting is required when the data being sorted do not fit into the main memory of a computing device (usually RAM) and instead they must reside in the slower external memory (usually a hard drive). Mergesort is suitable for external sorting.
It uses O(n) memory
Best/Average/Worst case = O(n lg n)

Unstable due to the pivot strategy.
In practice, one of the fastest sorting algorithms
Algorithm:
- Pick a pivot
- Reorder the list such that all elements < pivot are on the left, while all elements >= pivot are on the right
- Recursively sort each side
Comparison-based: examines elements by comparing them to other elements
Worst case occurs when the pivot is the unique minimum or maximum element
The best case for quick-sort occurs when the pivot is the middle element
Faster than MergeSort, but worst-case is O(n^2). Randomized algorithms can be used to prove that the average case for Quicksort is O(n lg n)
It uses O(lg n) memory
Best Case = O(n lg n); Average case = O(n lg n); Worst case = O(n^2)

Bubble sort is a simple algorithm that can be used efficiently on a list of any length that is nearly sorted.
Memory = O(1)
Best case = O(n); Worst/Average = O(n^2)

Unstable
Heapsort can be seen as an efficient version of selection sort, which works by determining the largest (or smallest) element of the list
Memory = O(1)
Best/Average/Worst = O(n lg n)

Usually on “real” data: Quick < Merge < Heap < I/S/B
On very short lists: quadratic sorts may have an advantage (so, some quick/merge implementations “bottom out” to these as base cases)
Stability
- Easily Made Stable: Insert, Merge, Bubble
- Challenging to Make Stable: Select, Quick
- Unstable: Heap
Memory use:
- Insert, Select, Heap, Bubble < Quick < Merge