Sorting Algorithms

Common Sorting Algorithms

1. Bubble Sort | Runtime : O(n²) average and worst case. Memory : O(1). In a bubble sort, we start at the beginning of the array and swap the first two elements if the first is greater than the second. Then we go to the next pair, and so on, continuously making sweeps of the array until it is sorted. In doing so, the smaller items slowly "bubble" up to the beginning of the list.
2. Selection Sort | Runtime : O(n²) average and worst case. Memory : O(1). Find the smallest element using a linear scan and move it to the front (swapping it with the front element). Then, find the second smallest and move it, again doing a linear scan. Continue doing this until all the elements are in place.
3. Merge Sort | Runtime : O(n log(n)) average and worst case. Memory : depends. Merge sort divides the array in half, sorts each of those halves, and then merges them back together. Each of those halves has the same sorting algorithm applied to it. Eventually, you are merging just two simgle-element arrays. It is the "merge" part that does all the heavy lifting. The merge method operates by copying all the elements from the target array segment into a helper array, keeping track of where the start of the left and right halves should be (helperLeft and helperRight). We then iterate through helper, copying the smaller element from each half into the array. At then end, we copy and remaining elements into the target array.
4. Quick Sort | Runtime : O(n log(n)) average, O(n²) worst case. Memory : O(log(n)) In quick sort, we pick a random element and partition the array, such that all numbers that are less than the partitioning element come before all elements that are greater than it. The partitioning can be performed efficiently through a series of swaps.
5. Radix Sort | Runtime : O(kn) Radix sort is a sorting algorithm for integers (and some other data types) that takes advantage of the fact that integers have a finite number of bits. In radix sort, we iterate through each digit of the number, grouping numbers by each digit. For example, if we have an array of integers, we might first sort by the first digit, so that the 0s are grouped together. Then, we sort each of these groupings by the next gdigit. We repeat this process sorting by each subsequent digit, until finally the whole array is sorted. Unlike comparison sorting algorithms, which cannot perform better than O(n log(n)) in the average case, radix sort has a runtime of O(kn), where n is the number of elements and k is the number of passes of the sorting algorithm.