Time complexity comparisonCompare
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(k) | Yes |
Merge sortHow it works
Split the array in half, sort each half recursively, then merge the two sorted halves. It is stable and always O(n log n), but it needs O(n) extra space for the merge.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","actorBkg":"#e7f5ff","actorBorder":"#1e1e1e","noteBkgColor":"#fff9db","noteBorderColor":"#1e1e1e"}}}%%
graph TD
A["38 27 43 3 9 82 10"] --> B["38 27 43 3"]
A --> C["9 82 10"]
B --> D["38 27"]
B --> E["43 3"]
C --> F["9 82"]
C --> G["10"]
D --> H["27 38"]
E --> I["3 43"]
F --> J["9 82"]
G --> K["10"]
H --> L["3 27 38 43"]
I --> L
J --> M["9 10 82"]
K --> M
L --> N["3 9 10 27 38 43 82"]
M --> N
class A,B,C,D,E,F,G red
class H,I,J,K yellow
class L,M blue
class N green
classDef orange fill:#ffd8a8,stroke:#1e1e1e,color:#1e1e1e
classDef blue fill:#a5d8ff,stroke:#1e1e1e,color:#1e1e1e
classDef green fill:#b2f2bb,stroke:#1e1e1e,color:#1e1e1e
classDef red fill:#ffc9c9,stroke:#1e1e1e,color:#1e1e1e
classDef violet fill:#d0bfff,stroke:#1e1e1e,color:#1e1e1e
classDef yellow fill:#ffec99,stroke:#1e1e1e,color:#1e1e1e
classDef grey fill:#e9ecef,stroke:#1e1e1e,color:#1e1e1efunction mergeSort(nums: number[]): number[] {
if (nums.length <= 1) return nums;
const mid = Math.floor(nums.length / 2);
const left = mergeSort(nums.slice(0, mid));
const right = mergeSort(nums.slice(mid));
return merge(left, right);
}
function merge(a: number[], b: number[]): number[] {
const result: number[] = [];
let i = 0, j = 0;
while (i < a.length && j < b.length) {
if (a[i] <= b[j]) result.push(a[i++]);
else result.push(b[j++]);
}
return result.concat(a.slice(i), b.slice(j));
}Quick sortHow it works
Pick a pivot, move everything smaller to its left and everything bigger to its right (this is called partitioning), then sort each side the same way. It sorts in place, using only O(log n) stack space, but bad pivots make it O(n²).
Partitioning around pivot 5
function quickSort(nums: number[], lo = 0, hi = nums.length - 1): void {
if (lo >= hi) return;
const pivotIdx = partition(nums, lo, hi);
quickSort(nums, lo, pivotIdx - 1);
quickSort(nums, pivotIdx + 1, hi);
}
function partition(nums: number[], lo: number, hi: number): number {
const pivot = nums[hi];
let i = lo;
for (let j = lo; j < hi; j++) {
if (nums[j] < pivot) {
[nums[i], nums[j]] = [nums[j], nums[i]];
i++;
}
}
[nums[i], nums[hi]] = [nums[hi], nums[i]];
return i;
}Which sort to useWhen to use
Merge sort
When stability matters, or when you need a guaranteed O(n log n).
Quick sort
The default for sorting in memory. Fastest in practice because it works on nearby memory (good cache use).
Heap sort
When you need O(1) extra space and do not need stability.
Counting / radix sort
When values are integers in a small, known range. O(n) time.
Built-in sort
In interviews, use nums.sort((a, b) => a - b) unless you are asked to write the sort yourself.
Common mistakesPitfalls
In the interviewIn the interview
Sorting is often the first step of a bigger solution. Always include its cost in your final complexity.
Frequently asked questionsFAQ
Which sorting algorithm should you use in practice?
The hybrid quicksort used by most standard libraries is the default, sorting in place with O(n log n) average time. For already-sorted or tiny inputs, insertion sort and Timsort's natural-run detection beat it, so choose based on data characteristics rather than a single theoretical curve.
What are the best and worst cases of quicksort?
Quicksort averages O(n log n) with randomized pivots, but poor pivot choice on already-sorted input degrades it to O(n^2). Library implementations avoid this with median-of-three or introsort, which switches to heapsort beyond a recursion bound, guaranteeing O(n log n) worst case.
When is counting sort better than comparison-based sorting?
Counting sort runs in O(n + k), where k is the value range, beating the O(n log n) lower bound of comparison sorts. It works only for integer keys with a bounded range, which is why it suits grades, ages, or small IDs and serves as a subroutine of radix sort.
Now explain sorting algorithms to me out loud
I'll give you interview problems and ask follow-ups, like a real interviewer.