Implementation of popular sorting algorithms in C++
Inserts the ith element in an i-1 length sorted list for i = 1,2,3...n Complexity : O(N^2)
Improves insertion sort with comparing elements that are far from each other. For each pass -where number of passes = K is a hyperparameter- it creates pass distanced sorted arrays, for pass = 2K-1, 2K-3 ... 5, 3, 1 Complexity : O(N^(4/3))
First, creates a max heap from array and performs n swap and n percolate down operations. Complexity : O(N) + O(N*logN)
Merge Sort is a divide and conquer algorithm that first divides the array into equal sized portions. Then conquers by merging sorted portions to build fully sorted array. Complexity : O(NlogN), + O(N) space complexity
Quick Sort is a divide and conquer algorithm. It chooses a pivot in each pass and orders the element in the current array in such a way that all the elements in current subarray that are less than pivot gathered in left side of the pivot and all the elements that are greater than the pivot is gathered in the right side. Complexity : O(NlogN) (average), O(N^2)(worst) Stack implementation is a little bit faster due to less function call overhead.
Radix Sort is not a comparison based sorting algorithm. It sorts the element from the least significant digit to most significant digit iteratively. Complexity : O(NK) where K is the number of digits of the largest element. (it has O(N) extra space complexity)
Considering both theoretical and practical performance, Radix Sort dominates the others when K is less than logN.