Overview of fast sorting algorithms: Quicksort, Merge sort, Heap sort and Radix sort
Image credit: Merge sort algorithm diagram from wikimedia commons
Let’s do a quick review of fast sorting algorithms. A fast sorting algorithm has an average runtime complexity of O(n log n) or better. The algorithms I am reviewing in this article are Quicksort, Merge sort, Heap sort and Radix sort.
This is by no means a comprehensive analysis of these algorithms, but more of an introduction or a refresher.
Quicksort, Merge sort and Heap sort are element comparison sorting algorithms, while Radix sort is not. What it means is that each of the three sorting algorithms operates on an array of elements that can be compared to each other. For example, array containing strings can be sorted using comparison sorting algorithm. Radix sort requires array elements to be integers (or data with integer keys).
Quicksort
Quick sort is a divide and conquer algorithm.
Divide and Conquer is a paradigm that is based on recursion. It has three parts: 1. Divide problem into subproblems. 2.Conquer subproblems by recursively solving them. 3.Combine the subproblems’ solutions into a solution to the original problem
This is how Quicksort works: we pick a pivot point, which is just an element in the array, and we sort the array, so that all the numbers that are smaller than the pivot point go to the left side, and the ones that are greater than the pivot point, go to the right side. We can pick a pivot in a few different ways: it can be the first element, the last element, random element, or element that is right in the middle. The partition process is the crucial process in Quicksort. It performs series of swaps and eventually sorts the whole array.
Quicksort runtime is: average/ best case O(n log n), worst case O(n²). The best case happens when the pivot is the middle element. The worst case happens when the pivot is greatest or smallest element.
Merge sort
Merge sort is also a divide a conquer algorithm. It takes input array and divides it into sub arrays, recursively sorts each sub array and then merges them. In terms of using divide and conquer, here is how it works:
- It divides by finding a midpoint in an array (divide by 2 then round down).
2. It conquers by recursively sorting each of the sub arrays created in the first step.
3. It combines the sorted arrays into one final sorted array.
Merge sort has a runtime of O(n log n) for average and worst cases.
Heap sort
Heap sort uses binary heap data structure.
Binary heap is a binary tree that is a complete tree and that is either a max heap or a min heap.
First, we need to build a max heap from the given input array. Then we take the root, which is the largest element, and replace it with the last item of the heap. Then we exclude the last element from the heap, but still keep it, because it is going to be a part of the resulting sorted array. We reduce the size of the heap by 1. Then we heapify the root of the tree. We continue repeating the steps until the size of the heap reaches 0, which means there is nothing left to sort.
Average time complexity of Heap Sort is O (n log n).
Radix sort
Radix sort is my favorite among the four, because it is a specialized sorting algorithm used for integers (and other data that can be sorted lexicographically).
The way it works is we sort numbers into buckets based on their radix.
Radix is the number of unique digits that is used to represent numbers in a positional numeral system. For example, in decimal system we use 10 numbers, which are 0 through 9.
We can sort starting with the least significant digit or the most significant digit. For example, if we have an array of integers, during the first pass we could sort them based on the 1st place, then on the second pass we sort them based on the 10th place, then we sort based on the 100s place, and so on.
Radix sort has a runtime (average case) of O(k n), where n is a number of elements and k is the number of digits for a particular positional numeral system, aka base (like 10 in decimal system).
