Sorting Algorithms at a Glance
You will almost never write a sorting algorithm from scratch in an interview, because the built-in sort is the right call. What interviewers do ask is how sorting algorithms compare: their best, average and worst case running times, how much extra memory they use, and whether they keep equal elements in their original order.
1) Quick Sort
Picks a pivot, moves smaller values to its left and larger values to its right, then sorts each side.
Time complexity
- Best: O(n log n)
- Average: O(n log n)
- Worst: O(n²)
Space complexity: O(log n)
2) Merge Sort
Splits the array in half, sorts both halves, then merges the two sorted halves.
Time complexity
- Best: O(n log n)
- Average: O(n log n)
- Worst: O(n log n)
Space complexity: O(n)
3) Heap Sort
Builds a heap, then repeatedly moves the largest remaining value to the end.
Time complexity
- Best: O(n log n)
- Average: O(n log n)
- Worst: O(n log n)
Space complexity: O(1)
4) Insertion Sort
Grows a sorted prefix by sliding each new value back into place.
Time complexity
- Best: O(n)
- Average: O(n²)
- Worst: O(n²)
Space complexity: O(1)
5) Timsort
Finds already sorted runs, sorts short runs with insertion sort, then merges them. Python and Java use it.
Time complexity
- Best: O(n)
- Average: O(n log n)
- Worst: O(n log n)
Space complexity: O(n)
6) Bubble Sort
Swaps neighbors that are out of order, pass after pass, until no swaps are needed.
Time complexity
- Best: O(n)
- Average: O(n²)
- Worst: O(n²)
Space complexity: O(1)
7) Shell Sort
Runs insertion sort on elements far apart first, then shrinks the gap until it is 1.
Time complexity
- Best: O(n log n)
- Average: Depends on the gap sequence
- Worst: O(n²)
Space complexity: O(1)
8) Bucket Sort
Spreads values into buckets by range, sorts each bucket, then joins them in order.
Time complexity
- Best: O(n + k)
- Average: O(n + k)
- Worst: O(n²)
Space complexity: O(n + k)
k is the number of buckets.
9) Radix Sort
Sorts numbers one digit at a time, from the least significant digit up, with a stable sort per digit.
Time complexity
- Best: O(nk)
- Average: O(nk)
- Worst: O(nk)
Space complexity: O(n + k)
k is the number of digits.
10) Counting Sort
Counts how often each value appears, then writes the values back out in order.
Time complexity
- Best: O(n + k)
- Average: O(n + k)
- Worst: O(n + k)
Space complexity: O(k)
k is the range of the values.
11) Selection Sort
Repeatedly finds the smallest remaining value and swaps it to the front.
Time complexity
- Best: O(n²)
- Average: O(n²)
- Worst: O(n²)
Space complexity: O(1)