- Insertion Sort
- Quick Sort
- Merge sort

# § Categorizing Sorting Algorithms

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

## § Algorithms

### § Selection Sort O(n^2)

- 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)

### § Insertion sort 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)

### § Mergesort O(n lg n)

- 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)

### § Quicksort 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)

### § Bublesort 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)

### § Heapsort O(n lg n)

- 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)

## § Comparison of different sorting algorithms

- 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