Sorting is one of the most fundamental operations in computer science. Almost every real-world application involves sorting at some point — displaying search results, ranking items, organizing data for binary search, or removing duplicates efficiently.
In simple language, sorting means arranging elements in a specific order (usually ascending or descending). The interesting part isn’t what sorting does — it’s how different algorithms do it, and why some are drastically faster than others.
Why Sorting Matters for Interviews
Many problems become trivially easy once the data is sorted. Two sum? Sort first, then use two pointers. Finding duplicates? Sort first, then check neighbors. Merge intervals? Sort by start time first.
Knowing when to sort (and what it costs) is a superpower in interviews.
The Basic Sorts (Quick Overview)
These are O(n²) algorithms. We won’t implement them all in detail, but we need to know they exist and why they’re slow.
Bubble Sort
Repeatedly swap adjacent elements if they’re in the wrong order. Like bubbles rising to the surface. Simple but painfully slow.
Selection Sort
Find the minimum element, put it first. Find the next minimum, put it second. Repeat. Also O(n²) — we scan the remaining array each time.
Insertion Sort
Build the sorted array one element at a time. Pick the next element, insert it into the correct position in the already-sorted portion. Actually decent for small or nearly-sorted arrays.
// Insertion sort -- good for small/nearly-sorted arrays
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let key = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // shift larger elements right
j--;
}
arr[j + 1] = key; // insert in correct position
}
return arr;
}# Insertion sort -- good for small/nearly-sorted arrays
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j] # shift larger elements right
j -= 1
arr[j + 1] = key # insert in correct position
return arr// Insertion sort -- good for small/nearly-sorted arrays
static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // shift larger elements right
j--;
}
arr[j + 1] = key; // insert in correct position
}
}Merge Sort — Divide and Conquer
Merge sort is the go-to O(n log n) algorithm that’s always O(n log n), no matter what input we throw at it. The idea is classic divide and conquer:
- Split the array in half
- Recursively sort each half
- Merge the two sorted halves together
The magic is in the merge step — combining two sorted arrays into one sorted array takes just O(n) time.
// Merge sort -- always O(n log n), stable sort
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(left, right) {
const result = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) result.push(left[i++]);
else result.push(right[j++]);
}
// add remaining elements
return result.concat(left.slice(i)).concat(right.slice(j));
}# Merge sort -- always O(n log n), stable sort
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
# add remaining elements
result.extend(left[i:])
result.extend(right[j:])
return result// Merge sort -- always O(n log n), stable sort
static void mergeSort(int[] arr, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) temp[k++] = arr[i++];
else temp[k++] = arr[j++];
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
System.arraycopy(temp, 0, arr, left, temp.length);
}Quick Sort — The Fast Gambler
Quick sort is usually the fastest in practice, but it has a weakness: its worst case is O(n²). The algorithm:
- Pick a pivot element
- Partition the array so everything smaller goes left, everything larger goes right
- Recursively sort the left and right parts
The pivot choice matters a lot. Bad pivot (like always picking the first element on sorted data) gives O(n²). Random pivot gives O(n log n) on average.
// Quick sort -- O(n log n) average, in-place
function quickSort(arr, low = 0, high = arr.length - 1) {
if (low >= high) return;
const pivotIdx = partition(arr, low, high);
quickSort(arr, low, pivotIdx - 1);
quickSort(arr, pivotIdx + 1, high);
}
function partition(arr, low, high) {
const pivot = arr[high]; // pick last element as pivot
let i = low - 1;
for (let j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]]; // swap
}
}
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
return i + 1; // pivot's final position
}# Quick sort -- O(n log n) average, in-place
def quick_sort(arr, low=0, high=None):
if high is None:
high = len(arr) - 1
if low >= high:
return
pivot_idx = partition(arr, low, high)
quick_sort(arr, low, pivot_idx - 1)
quick_sort(arr, pivot_idx + 1, high)
def partition(arr, low, high):
pivot = arr[high] # pick last element as pivot
i = low - 1
for j in range(low, high):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i] # swap
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1 # pivot's final position// Quick sort -- O(n log n) average, in-place
static void quickSort(int[] arr, int low, int high) {
if (low >= high) return;
int pivotIdx = partition(arr, low, high);
quickSort(arr, low, pivotIdx - 1);
quickSort(arr, pivotIdx + 1, high);
}
static int partition(int[] arr, int low, int high) {
int pivot = arr[high]; // pick last element as pivot
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
}
}
int temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp;
return i + 1; // pivot's final position
}Built-in Sorts with Custom Comparators
In interviews, we almost never write merge sort from scratch. We use the language’s built-in sort with a custom comparator. This is essential to know.
// Sort numbers (default .sort() is lexicographic!)
const nums = [10, 9, 2, 30];
nums.sort((a, b) => a - b); // ascending: [2, 9, 10, 30]
nums.sort((a, b) => b - a); // descending: [30, 10, 9, 2]
// Sort objects by a property
const people = [{name: "Bob", age: 25}, {name: "Alice", age: 30}];
people.sort((a, b) => a.age - b.age); // sort by age ascending
// Sort strings by length
const words = ["banana", "kiwi", "apple"];
words.sort((a, b) => a.length - b.length);# Sort numbers
nums = [10, 9, 2, 30]
nums.sort() # in-place ascending: [2, 9, 10, 30]
sorted_desc = sorted(nums, reverse=True) # new list descending
# Sort objects by a key
people = [{"name": "Bob", "age": 25}, {"name": "Alice", "age": 30}]
people.sort(key=lambda p: p["age"]) # sort by age ascending
# Sort strings by length
words = ["banana", "kiwi", "apple"]
words.sort(key=lambda w: len(w))// Sort numbers
int[] nums = {10, 9, 2, 30};
Arrays.sort(nums); // ascending: [2, 9, 10, 30]
// Sort objects with comparator
String[] words = {"banana", "kiwi", "apple"};
Arrays.sort(words, (a, b) -> a.length() - b.length()); // by length
// Sort a list of objects
List<int[]> intervals = new ArrayList<>();
intervals.sort((a, b) -> a[0] - b[0]); // sort by first elementGotcha: JavaScript’s default .sort() converts elements to strings. [10, 9, 2].sort() gives [10, 2, 9]. Always pass a comparator for numbers.
Stability — Does Order of Equal Elements Matter?
A stable sort preserves the relative order of elements with equal keys. If we sort students by grade and two students both have an A, a stable sort keeps them in their original order.
- Stable: Merge sort, insertion sort, Python’s Timsort, Java’s Arrays.sort for objects
- Unstable: Quick sort, heap sort
When does stability matter? When we sort by multiple criteria. Sort by name first, then by grade — a stable sort preserves the name ordering within each grade.
The Big Comparison Table
| Algorithm | Best | Average | Worst | Space | Stable? |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion 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 |
When to Use Which
- Merge sort: When we need guaranteed O(n log n) and stability. Great for linked lists (no extra space needed).
- Quick sort: Default choice for arrays. Fastest in practice due to cache efficiency. Most language built-in sorts use a variant of quick sort.
- Insertion sort: Small arrays (n < 20) or nearly sorted data. Many built-in sorts switch to insertion sort for small subarrays.
- Heap sort: When we need O(n log n) guarantee with O(1) space. Rarely used directly — we’ll cover heaps in a later topic.
In interviews, the key insight is: sorting costs O(n log n), so if our solution is already O(n log n) or worse, sorting is “free” — it doesn’t change the overall complexity.