From O(n²) basics to O(n log n) workhorses and binary search. Know the trade-offs, write the code, crush the interviews.
Sorting is one of the most fundamental operations in computer science. Nearly every system you interact with uses sorting under the hood -- databases order query results, search engines rank pages, and operating systems schedule processes.
In interviews, you rarely need to implement a sorting algorithm from scratch. But you absolutely need to know their complexities, trade-offs, and when to use each one. For binary search, you need to be able to write it cold.
| 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 |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(k) | Yes |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n + k) | Yes |
A sorting algorithm is stable if it preserves the relative order of elements that have equal keys. For example, if you sort a list of students by grade and two students both have a B, a stable sort keeps them in the same relative order they were in before sorting.
Input: [("Alice", B), ("Bob", A), ("Charlie", B)]
Stable sort by grade: [("Bob", A), ("Alice", B), ("Charlie", B)] -- Alice still before Charlie
Unstable sort by grade: [("Bob", A), ("Charlie", B), ("Alice", B)] -- order of B's might flip
Stability matters when you sort by multiple keys. Sort by secondary key first, then by primary key with a stable sort, and the secondary ordering is preserved within groups.
Concept: Repeatedly walk through the array and swap adjacent elements if they are in the wrong order. After each full pass, the largest unsorted element "bubbles" up to its correct position at the end.
Pass 1:
[5, 3, 8, 1, 2] → swap 5,3 → [3, 5, 8, 1, 2]
[3, 5, 8, 1, 2] → no swap → [3, 5, 8, 1, 2]
[3, 5, 8, 1, 2] → swap 8,1 → [3, 5, 1, 8, 2]
[3, 5, 1, 8, 2] → swap 8,2 → [3, 5, 1, 2, 8]
// 8 is now in its final position
Pass 2:
[3, 5, 1, 2, 8] → no swap → [3, 5, 1, 2, 8]
[3, 5, 1, 2, 8] → swap 5,1 → [3, 1, 5, 2, 8]
[3, 1, 5, 2, 8] → swap 5,2 → [3, 1, 2, 5, 8]
// 5 is now in its final position
Pass 3:
[3, 1, 2, 5, 8] → swap 3,1 → [1, 3, 2, 5, 8]
[1, 3, 2, 5, 8] → swap 3,2 → [1, 2, 3, 5, 8]
// 3 is now in its final position
Pass 4:
[1, 2, 3, 5, 8] → no swaps → DONE!
Result: [1, 2, 3, 5, 8]Pythondef bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
# If no swaps happened, array is already sorted
if not swapped:
break
return arr
# Example
print(bubble_sort([5, 3, 8, 1, 2])) # [1, 2, 3, 5, 8]
JavaScriptfunction bubbleSort(arr) {
const n = arr.length;
for (let i = 0; i < n; i++) {
let swapped = false;
for (let j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
swapped = true;
}
}
// If no swaps happened, array is already sorted
if (!swapped) break;
}
return arr;
}
// Example
console.log(bubbleSort([5, 3, 8, 1, 2])); // [1, 2, 3, 5, 8]
Bubble sort is O(n²) in the average and worst case. It does far too many comparisons and swaps. Never use it in production code. The only scenario where it's acceptable is a nearly-sorted, very small array -- and even then, insertion sort is better.
Concept: Find the minimum element in the unsorted portion, swap it with the first unsorted element, and move the boundary one step to the right. Repeat until the entire array is sorted.
Pass 1: Find min in [29, 10, 14, 37, 13] → min is 10 at index 1
Swap arr[0] and arr[1]: [10, 29, 14, 37, 13]
Sorted: [10 | 29, 14, 37, 13]
Pass 2: Find min in [29, 14, 37, 13] → min is 13 at index 4
Swap arr[1] and arr[4]: [10, 13, 14, 37, 29]
Sorted: [10, 13 | 14, 37, 29]
Pass 3: Find min in [14, 37, 29] → min is 14 at index 2
Already in place: [10, 13, 14, 37, 29]
Sorted: [10, 13, 14 | 37, 29]
Pass 4: Find min in [37, 29] → min is 29 at index 4
Swap arr[3] and arr[4]: [10, 13, 14, 29, 37]
Sorted: [10, 13, 14, 29 | 37]
Result: [10, 13, 14, 29, 37]Pythondef selection_sort(arr):
n = len(arr)
for i in range(n):
# Find the index of the minimum element in unsorted portion
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
# Swap the found minimum with the first unsorted element
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
# Example
print(selection_sort([29, 10, 14, 37, 13])) # [10, 13, 14, 29, 37]
JavaScriptfunction selectionSort(arr) {
const n = arr.length;
for (let i = 0; i < n; i++) {
// Find the index of the minimum element in unsorted portion
let minIdx = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
// Swap the found minimum with the first unsorted element
[arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
}
return arr;
}
// Example
console.log(selectionSort([29, 10, 14, 37, 13])); // [10, 13, 14, 29, 37]
Selection sort is not stable because the swap can move equal elements past each other. It is also O(n²) in all cases -- even if the array is already sorted, it still scans for the minimum every pass. Don't use it in practice.
Concept: Build the sorted array one element at a time. Take each element and insert it into its correct position in the already-sorted portion. Think of it like sorting a hand of playing cards -- you pick up each card and slide it into the right spot.
Start: sorted portion = [5], pick up 2
2 < 5, shift 5 right, insert 2: [2, 5, 4, 6, 1, 3]
Pick up 4:
4 < 5, shift 5 right. 4 > 2, stop. Insert 4: [2, 4, 5, 6, 1, 3]
Pick up 6:
6 > 5, already in place: [2, 4, 5, 6, 1, 3]
Pick up 1:
1 < 6, shift. 1 < 5, shift. 1 < 4, shift. 1 < 2, shift.
Insert 1 at front: [1, 2, 4, 5, 6, 3]
Pick up 3:
3 < 6, shift. 3 < 5, shift. 3 < 4, shift. 3 > 2, stop.
Insert 3: [1, 2, 3, 4, 5, 6]
Result: [1, 2, 3, 4, 5, 6]Pythondef insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i] # The element to insert
j = i - 1
# Shift elements of the sorted portion that are greater than key
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key # Insert into correct position
return arr
# Example
print(insertion_sort([5, 2, 4, 6, 1, 3])) # [1, 2, 3, 4, 5, 6]
JavaScriptfunction insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
const key = arr[i]; // The element to insert
let j = i - 1;
// Shift elements of the sorted portion that are greater than key
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key; // Insert into correct position
}
return arr;
}
// Example
console.log(insertionSort([5, 2, 4, 6, 1, 3])); // [1, 2, 3, 4, 5, 6]
Unlike bubble and selection sort, insertion sort is actually used in practice. Python's built-in sorted() uses Timsort, which is a hybrid of merge sort and insertion sort. Timsort uses insertion sort for small subarrays (typically < 64 elements) because insertion sort has low overhead and is very fast on small or nearly-sorted data.
Concept: Divide the array in half, recursively sort each half, then merge the two sorted halves back together. This is a classic divide and conquer algorithm.
SPLIT phase (divide into halves):
[38, 27, 43, 3, 9, 82, 10]
/ \
[38, 27, 43, 3] [9, 82, 10]
/ \ / \
[38, 27] [43, 3] [9, 82] [10]
/ \ / \ / \
[38] [27] [43] [3] [9] [82]
MERGE phase (combine sorted halves):
[38] [27] [43] [3] [9] [82] [10]
\ / \ / \ /
[27, 38] [3, 43] [9, 82] [10]
\ / \ /
[3, 27, 38, 43] [9, 10, 82]
\ /
[3, 9, 10, 27, 38, 43, 82]Pythondef merge_sort(arr):
# Base case: array of length 0 or 1 is already sorted
if len(arr) <= 1:
return arr
# DIVIDE: split array into two halves
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # Recursively sort left half
right = merge_sort(arr[mid:]) # Recursively sort right half
# MERGE: combine two sorted halves
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
# Compare elements from both halves, pick the smaller one
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= makes it stable
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# Append remaining elements (one half may have leftovers)
result.extend(left[i:])
result.extend(right[j:])
return result
# Example
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]
JavaScriptfunction mergeSort(arr) {
// Base case: array of length 0 or 1 is already sorted
if (arr.length <= 1) return arr;
// DIVIDE: split array into two halves
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid)); // Recursively sort left
const right = mergeSort(arr.slice(mid)); // Recursively sort right
// MERGE: combine two sorted halves
return merge(left, right);
}
function merge(left, right) {
const result = [];
let i = 0, j = 0;
// Compare elements from both halves, pick the smaller one
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) { // <= makes it stable
result.push(left[i]);
i++;
} else {
result.push(right[j]);
j++;
}
}
// Append remaining elements
return result.concat(left.slice(i)).concat(right.slice(j));
}
// Example
console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));
// [3, 9, 10, 27, 38, 43, 82]
sorted() (Timsort is a hybrid of merge sort + insertion sort), Java's Arrays.sort() for objects, external sorting (sorting data that doesn't fit in memory).Merge sort is a top interview topic. You should be able to write it from memory. The key insight is that merging two sorted arrays is O(n) -- you just compare the fronts of both arrays and pick the smaller one.
Concept: Pick a "pivot" element, then partition the array so that all elements less than the pivot come before it and all elements greater come after it. Recursively sort the two partitions.
The partition is the heart of quick sort. Here is how Lomuto's partition scheme works:
i that tracks where the next "smaller than pivot" element should go.j. If arr[j] < pivot, swap arr[i] and arr[j], then increment i.i. Now everything left of i is smaller, everything right is larger.pivot = 70 (last element), i = 0
j=0: arr[0]=10 < 70 → swap arr[0],arr[0], i=1 [10, 80, 30, 90, 40, 50, 70]
j=1: arr[1]=80 > 70 → skip [10, 80, 30, 90, 40, 50, 70]
j=2: arr[2]=30 < 70 → swap arr[1],arr[2], i=2 [10, 30, 80, 90, 40, 50, 70]
j=3: arr[3]=90 > 70 → skip [10, 30, 80, 90, 40, 50, 70]
j=4: arr[4]=40 < 70 → swap arr[2],arr[4], i=3 [10, 30, 40, 90, 80, 50, 70]
j=5: arr[5]=50 < 70 → swap arr[3],arr[5], i=4 [10, 30, 40, 50, 80, 90, 70]
Swap pivot (70) into position i=4:
[10, 30, 40, 50, 70, 90, 80]
Now: [10, 30, 40, 50] < 70 < [90, 80]
Recursively sort left and right partitions.Pythondef quick_sort(arr):
# Simple version using list comprehensions (Pythonic but uses extra space)
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2] # Choose middle element as pivot
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
# In-place version (more efficient, what interviewers want to see)
def quick_sort_inplace(arr, low=0, high=None):
if high is None:
high = len(arr) - 1
if low < high:
# Partition and get pivot index
pivot_idx = partition(arr, low, high)
# Recursively sort left and right of pivot
quick_sort_inplace(arr, low, pivot_idx - 1)
quick_sort_inplace(arr, pivot_idx + 1, high)
return arr
def partition(arr, low, high):
pivot = arr[high] # Choose last element as pivot
i = low # Pointer for "smaller than pivot" boundary
for j in range(low, high):
if arr[j] < pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
# Place pivot in its correct position
arr[i], arr[high] = arr[high], arr[i]
return i
# Example
print(quick_sort([10, 80, 30, 90, 40, 50, 70]))
# [10, 30, 40, 50, 70, 80, 90]
print(quick_sort_inplace([10, 80, 30, 90, 40, 50, 70]))
# [10, 30, 40, 50, 70, 80, 90]
JavaScript// Simple version (uses extra space)
function quickSort(arr) {
if (arr.length <= 1) return arr;
const pivot = arr[Math.floor(arr.length / 2)];
const left = arr.filter(x => x < pivot);
const middle = arr.filter(x => x === pivot);
const right = arr.filter(x => x > pivot);
return [...quickSort(left), ...middle, ...quickSort(right)];
}
// In-place version (efficient, interview-ready)
function quickSortInPlace(arr, low = 0, high = arr.length - 1) {
if (low < high) {
const pivotIdx = partition(arr, low, high);
quickSortInPlace(arr, low, pivotIdx - 1);
quickSortInPlace(arr, pivotIdx + 1, high);
}
return arr;
}
function partition(arr, low, high) {
const pivot = arr[high]; // Choose last element as pivot
let i = low; // Boundary pointer
for (let j = low; j < high; j++) {
if (arr[j] < pivot) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
}
}
// Place pivot in correct position
[arr[i], arr[high]] = [arr[high], arr[i]];
return i;
}
// Example
console.log(quickSort([10, 80, 30, 90, 40, 50, 70]));
// [10, 30, 40, 50, 70, 80, 90]
Quick sort is generally the fastest comparison-based sorting algorithm in practice due to excellent cache locality and low constant factors. Most standard library sorts (C's qsort, C++'s std::sort) use some variant of quick sort (often introsort, which falls back to heap sort if recursion gets too deep).
O(n²) occurs when: The pivot is always the min or max element (e.g., already-sorted input with first-element pivot).
Fix: Use random pivot selection or median-of-three. This makes worst case astronomically unlikely -- O(n log n) expected.
Concept: Build a max heap from the array, then repeatedly extract the maximum element and place it at the end.
Heaps are covered in detail on the Advanced Data Structures page, including heap implementation, heapify, and priority queues.
These are non-comparison sorts. They don't compare elements to each other -- instead, they exploit the structure of the data to sort faster than O(n log n).
When to use: You know the range of values is small (for example, sorting grades 0-100, or characters a-z).
Pythondef counting_sort(arr, max_val):
# Count occurrences of each value
count = [0] * (max_val + 1)
for num in arr:
count[num] += 1
# Build sorted array from counts
result = []
for val in range(max_val + 1):
result.extend([val] * count[val])
return result
# Example: sorting grades (range 0-5)
print(counting_sort([4, 2, 2, 8, 3, 3, 1], 8))
# [1, 2, 2, 3, 3, 4, 8]
JavaScriptfunction countingSort(arr, maxVal) {
const count = new Array(maxVal + 1).fill(0);
for (const num of arr) count[num]++;
const result = [];
for (let val = 0; val <= maxVal; val++) {
for (let i = 0; i < count[val]; i++) {
result.push(val);
}
}
return result;
}
console.log(countingSort([4, 2, 2, 8, 3, 3, 1], 8));
// [1, 2, 2, 3, 3, 4, 8]
Concept: Sort numbers digit by digit, starting from the least significant digit to the most significant. Uses counting sort (or any stable sort) as a subroutine for each digit.
Non-comparison sorts only work with specific data types (integers, strings of fixed length). They cannot sort arbitrary objects. For general-purpose sorting, you need comparison-based algorithms.
Prerequisite: The array must be sorted.
Concept: Compare the target with the middle element. If the target is smaller, search the left half. If larger, search the right half. Eliminate half the remaining elements with each comparison.
Each step cuts the search space in half. Starting with n elements: n → n/2 → n/4 → ... → 1. The number of steps to go from n to 1 by halving is log&sub2;(n). For an array of 1,000,000 elements, binary search takes at most ~20 comparisons.
Pythondef binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2 # or left + (right - left) // 2 to avoid overflow
if arr[mid] == target:
return mid # Found it!
elif arr[mid] < target:
left = mid + 1 # Target is in right half
else:
right = mid - 1 # Target is in left half
return -1 # Not found
# Example
arr = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(arr, 7)) # 3 (index)
print(binary_search(arr, 4)) # -1 (not found)
JavaScriptfunction binarySearch(arr, target) {
let left = 0, right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
// Example
const arr = [1, 3, 5, 7, 9, 11, 13];
console.log(binarySearch(arr, 7)); // 3
console.log(binarySearch(arr, 4)); // -1
Pythondef binary_search_recursive(arr, target, left=0, right=None):
if right is None:
right = len(arr) - 1
if left > right:
return -1 # Base case: not found
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_recursive(arr, target, mid + 1, right)
else:
return binary_search_recursive(arr, target, left, mid - 1)
JavaScriptfunction binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
if (left > right) return -1;
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) return binarySearchRecursive(arr, target, mid + 1, right);
return binarySearchRecursive(arr, target, left, mid - 1);
}
Find the first position where target could be inserted to keep the array sorted. If target exists, returns its leftmost index.
Pythondef bisect_left(arr, target):
left, right = 0, len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] < target:
left = mid + 1
else:
right = mid # Don't skip mid -- it might be the answer
return left
# Example: [1, 2, 2, 2, 3, 4]
# bisect_left(arr, 2) = 1 (leftmost index of 2)
JavaScriptfunction bisectLeft(arr, target) {
let left = 0, right = arr.length;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] < target) left = mid + 1;
else right = mid;
}
return left;
}
Find the first position after all occurrences of target.
Pythondef bisect_right(arr, target):
left, right = 0, len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] <= target:
left = mid + 1 # Skip past equal elements
else:
right = mid
return left
# Example: [1, 2, 2, 2, 3, 4]
# bisect_right(arr, 2) = 4 (first index after all 2s)
JavaScriptfunction bisectRight(arr, target) {
let left = 0, right = arr.length;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] <= target) left = mid + 1;
else right = mid;
}
return left;
}
A sorted array has been rotated at some pivot. For example, [4, 5, 6, 7, 0, 1, 2]. Find a target value in O(log n).
Key insight: At least one half of the array (left or right of mid) is always sorted. Determine which half is sorted, then check if the target falls in that range.
Pythondef search_rotated(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
# Left half is sorted
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1 # Target is in sorted left half
else:
left = mid + 1 # Target is in right half
# Right half is sorted
else:
if nums[mid] < target <= nums[right]:
left = mid + 1 # Target is in sorted right half
else:
right = mid - 1 # Target is in left half
return -1
# Example
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0)) # 4
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 3)) # -1
JavaScriptfunction searchRotated(nums, target) {
let left = 0, right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] === target) return mid;
// Left half is sorted
if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
// Right half is sorted
} else {
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
console.log(searchRotated([4, 5, 6, 7, 0, 1, 2], 0)); // 4
console.log(searchRotated([4, 5, 6, 7, 0, 1, 2], 3)); // -1
The most common binary search bug is off-by-one errors. Pay close attention to: (1) left <= right vs left < right, (2) mid + 1 vs mid, and (3) using right = len(arr) vs right = len(arr) - 1. These differ between "find exact" and "find insertion point" variants.
In practice, you will almost always use your language's built-in sort. But you need to know how to use it correctly and what is happening under the hood.
Python# sorted() returns a new list (does not modify original)
nums = [3, 1, 4, 1, 5, 9]
sorted_nums = sorted(nums) # [1, 1, 3, 4, 5, 9]
print(nums) # [3, 1, 4, 1, 5, 9] (unchanged)
# list.sort() sorts in-place (modifies original, returns None)
nums.sort()
print(nums) # [1, 1, 3, 4, 5, 9]
# Reverse sort
sorted(nums, reverse=True) # [9, 5, 4, 3, 1, 1]
# Custom key function
words = ["banana", "apple", "cherry"]
sorted(words, key=len) # ["apple", "banana", "cherry"]
# Sort by multiple criteria: sort tuples by second element, then first
pairs = [(2, "b"), (1, "a"), (2, "a"), (1, "b")]
sorted(pairs, key=lambda x: (x[1], x[0]))
# [(1, 'a'), (2, 'a'), (1, 'b'), (2, 'b')]
# Sort objects by attribute
students = [{"name": "Alice", "gpa": 3.5}, {"name": "Bob", "gpa": 3.9}]
sorted(students, key=lambda s: s["gpa"], reverse=True)
# [{"name": "Bob", "gpa": 3.9}, {"name": "Alice", "gpa": 3.5}]
JavaScript// Array.sort() sorts IN-PLACE and returns the array
const nums = [3, 1, 4, 1, 5, 9];
nums.sort();
console.log(nums); // [1, 1, 3, 4, 5, 9] ...or IS IT?
By default, Array.sort() converts elements to strings and sorts lexicographically! This means [10, 9, 80].sort() gives [10, 80, 9] because "10" < "80" < "9" as strings. You must ALWAYS provide a comparator for numbers.
JavaScript// ALWAYS use a comparator for numbers
const nums = [10, 9, 80, 3, 1];
// Ascending sort
nums.sort((a, b) => a - b); // [1, 3, 9, 10, 80]
// Descending sort
nums.sort((a, b) => b - a); // [80, 10, 9, 3, 1]
// Sort strings (default works fine for strings)
const words = ["banana", "apple", "cherry"];
words.sort(); // ["apple", "banana", "cherry"]
// Sort by string length
words.sort((a, b) => a.length - b.length);
// Sort objects by property
const students = [
{ name: "Alice", gpa: 3.5 },
{ name: "Bob", gpa: 3.9 }
];
students.sort((a, b) => b.gpa - a.gpa);
// [{name: "Bob", gpa: 3.9}, {name: "Alice", gpa: 3.5}]
// Non-destructive sort (create a copy first)
const original = [3, 1, 2];
const sorted = [...original].sort((a, b) => a - b);
// original is still [3, 1, 2]
Python: Uses Timsort (hybrid merge sort + insertion sort). Always O(n log n), stable.
JavaScript: Implementation varies. V8 (Chrome/Node) uses Timsort. SpiderMonkey (Firefox) uses merge sort. All modern engines guarantee stable sort as of ES2019.
These problems test your understanding of sorting algorithms and binary search. Focus on understanding the patterns, not just memorizing solutions.
| Problem | Difficulty | Key Concept |
|---|---|---|
| 56. Merge Intervals | Medium | Sort + merge overlapping |
| 75. Sort Colors | Medium | Dutch national flag / counting sort |
| 215. Kth Largest Element | Medium | Quick select / heap |
| 33. Search in Rotated Sorted Array | Medium | Modified binary search |
| 153. Find Min in Rotated Sorted Array | Medium | Binary search |
| 74. Search a 2D Matrix | Medium | Binary search on 2D |
| 4. Median of Two Sorted Arrays | Hard | Binary search on partition |
Problem: Given an array of intervals [[start, end], ...], merge all overlapping intervals.
Approach: Sort by start time, then iterate. If the current interval overlaps with the previous one (current start <= previous end), merge them by extending the end. Otherwise, add the current interval to the result.
Pythondef merge(intervals):
# Sort by start time
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
# If current overlaps with last merged interval
if start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end) # Extend end
else:
merged.append([start, end])
return merged
# Example
print(merge([[1,3],[2,6],[8,10],[15,18]]))
# [[1, 6], [8, 10], [15, 18]]
JavaScriptfunction merge(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
const merged = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
const [start, end] = intervals[i];
const last = merged[merged.length - 1];
if (start <= last[1]) {
last[1] = Math.max(last[1], end);
} else {
merged.push([start, end]);
}
}
return merged;
}
console.log(merge([[1,3],[2,6],[8,10],[15,18]]));
// [[1, 6], [8, 10], [15, 18]]
Problem: Search for a target in an m x n matrix where each row is sorted and the first element of each row is greater than the last element of the previous row.
Approach: Treat the 2D matrix as a flattened sorted array. Use binary search with index conversion: row = mid // cols, col = mid % cols.
Pythondef search_matrix(matrix, target):
rows, cols = len(matrix), len(matrix[0])
left, right = 0, rows * cols - 1
while left <= right:
mid = (left + right) // 2
# Convert 1D index to 2D coordinates
val = matrix[mid // cols][mid % cols]
if val == target:
return True
elif val < target:
left = mid + 1
else:
right = mid - 1
return False
JavaScriptfunction searchMatrix(matrix, target) {
const rows = matrix.length, cols = matrix[0].length;
let left = 0, right = rows * cols - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
const val = matrix[Math.floor(mid / cols)][mid % cols];
if (val === target) return true;
else if (val < target) left = mid + 1;
else right = mid - 1;
}
return false;
}
Full solution with detailed explanation is in Section 10: Binary Search above.
Start with Merge Intervals and Search in Rotated Sorted Array -- they appear in almost every interview prep list. Then tackle Kth Largest Element (introduces quick select) and Search a 2D Matrix. Save Median of Two Sorted Arrays for last -- it is genuinely hard.
Test your understanding of sorting algorithms and binary search.
[10, 9, 80].sort() in JavaScript?.sort() converts elements to strings and sorts lexicographically. As strings: "10" < "80" < "9" (because "1" < "8" < "9"). To sort numbers correctly, you must use .sort((a, b) => a - b).