Sorting Algorithms
Yet another conglomeration of sorting algorithms
The Basics
Sorting Algorithm? In easiest terms, putting elements of a list in a certain order.
Sorting In Place? Without any extra space requirement.
Stable? Resulting sorted array maintains the order of elements, i.e. if two objects with equal keys appear in the same order in input array, they would appear in the same order in the output array as well.
Online? Processing can be done piece-by-piece in a serial fashion, i.e., without having the entire input available from the start.
Bubble Sort
Basic Idea — Swap adjacent elements if they are in wrong order.
- Worst and Average Case Time Complexity: O(n²). Worst case occurs when array is reverse sorted.
- Best Case Time Complexity: O(n) Best case occurs when array is already sorted.
- Auxiliary Space: O(1)
- Sorting In Place: Yes
- Stable: Yes
Insertion Sort
Basic Idea — In every iteration(i) find the correct position of the element(i) (Just what you do while playing cards). Take it from the name — ‘insert’ element at correct position.
- Worst and Average Case Time Complexity: O(n²). Worst case occurs when array is reverse sorted.
- Best Case Time Complexity:O(n). Best case occurs when array is already sorted.
- Auxiliary Space: O(1)
- Sorting In Place: Yes
- Stable: Yes
- Online: Yes
Selection Sort
Basic Idea — finding the minimum or maximum element in an unsorted array and then putting it in its correct position in a sorted array.
- Worst and Average Case Time Complexity: O(n²). Worst case occurs when array is reverse sorted.
- Best Case Time Complexity:O(n). Best case occurs when array is already sorted.
- Auxiliary Space: O(1)
- Sorting In Place: Yes
- Stable: Yes
The Mains
Merge Sort
Basic Idea — divide-and-conquer approach; based on the idea of breaking down a list into several sub-lists until each sublist consists of a single element and merging those sublists in a manner that results into a sorted list.
The list of size N is divided into a max of logN parts, and the merging of all sublists into a single list takes O(N) time
- Worst and Average Case Time Complexity: O(nlog(n))
- Best Case Time Complexity: O(nlog(n))
- Auxiliary Space: O(n)
- Sorting In Place: No
- Stable:Yes
Quick Sort
Basic Idea — divide-and-conquer approach; based on the idea of choosing one element as a pivot element and partitioning the array around it such that: Left side of pivot contains all the elements that are less than the pivot element Right side contains all elements greater than the pivot.
- Worst and Average Case Time Complexity: O(n²) , O(nlog(n))
- Best Case Time Complexity: O(nlogn)
- Auxiliary Space: O(n)
- Sorting In Place: Yes
- Stable:Yes
Counting Sort
Basic Idea — ‘count’ the occurances of each distinct element in the array; store it in auxillary array; use those counts to compute an item’s index in the final, sorted array.
- Worst and Average Case Time Complexity: O(n+k)
- Best Case Time Complexity:O(n+k)
- Auxiliary Space: O(k) { where k=maximum element of input array}
- Sorting In Place: Yes
- Stable:Yes
Radix Sort
Basic Idea — sort the numbers from Least Significant Bit (LSB) to Most Significant Bit (MSB) ; an improvement to counting sort when ‘k’- the largest element in the array, goes to n².
Get Nidhi Ranjan’s stories in your inbox
Join Medium for free to get updates from this writer.
For each digit i where i varies from the least significant digit to the most significant digit of a number, sort input array using Counting Sort algorithm according to ith digit.
- Worst and Average Case Time Complexity: O(nk)
- Best Case Time Complexity: O(nk)
- Auxiliary Space: O(n+k)
- Sorting In Place: Yes
- Stable: No
Heap Sort
Basic Idea — similar to Selection Sort; convert array into a binary heap structure for efficient retrieval and removal of the maximal element. We repeatedly “remove” the maximal element from the heap, placing it in the back of the array; hence building the sorted list from back to front.
- Worst and Average Case Time Complexity: O(nlogn)
- Best Case Time Complexity: O(nlogn)
- Auxiliary Space: O(1)
- Sorting In Place: Yes
- Stable: No
Bucket Sort
Basic Idea — good for input in a particular range; divide input into different ‘buckets’, sort the bucket individually(using any sorting algorithm).
- Worst and Average Case Time Complexity: O(n²), O(n+k)
- Best Case Time Complexity: O(n+k)
- Auxiliary Space: O(n)
- Sorting In Place: No
- Stable: No
Tree Sort
Basic Idea — create a Binary Search Tree from the input array; do in-order traversal to fetch the sorted array
- Worst and Average Case Time Complexity: O(n*log(n))
- Best Case Time Complexity: O(n*log(n))
- Auxiliary Space: O(n)
- Sorting In Place: No
- Stable: No
Shell Sort
Basic Idea — variation of Insertion Sort; we try and sort the array in sublists of length (h). An array is said to be h-sorted if all sublists of every h’th element is sorted; after h-sorting the array, we reduce the value of h until it becomes 1, ie, every adjacent element is in a sorted position.
- Worst and Average Case Time Complexity: O(n*(log(n))²)
- Best Case Time Complexity: O(n*(log(n))²)
- Auxiliary Space: O(n)
- Sorting In Place: Yes
- Stable: No
That’s all folks. You can check out more sorting algorithms out at GeeksforGeeks.
I’ve used GeeksforGeeks, Github & Hackerearth for this compendium :)








