 Index | About | Me | Jump to Menu Section

# Sorting algorithms

• 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