Sorting Algorithms

Back to DSA & Algorithms/00 - Roadmap Overview

---

Why Know Sorting?

FAANG won't ask you to implement MergeSort from scratch often, but they will expect you to:

1. Know time/space complexity of each algorithm instantly
2. Pick the right sorting approach for a given constraint
3. Know when to use a custom comparator
4. Understand stability and in-place properties

---

The Comparison Table (Memorize This)

• Stable: Equal elements keep their original relative order
• k = range of values, d = number of digits

---

The Big Three You Must Know

1. Merge Sort (Divide and Conquer)

Split in half, sort each half, merge. Guaranteed O(n log n). Used in linked list sorting.

java
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);
}

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);
}

When to use: Linked lists (no random access needed), when stability matters, when you need guaranteed O(n log n).

2. Quick Sort (Partition)

Pick a pivot, partition elements around it, recurse on each side.

java
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);
}

int partition(int[] arr, int low, int high) {
    int pivot = arr[high]; // Choose last element as pivot
    int i = low;           // Boundary of "less than pivot" region

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            swap(arr, i, j);
            i++;
        }
    }
    swap(arr, i, high); // Place pivot at correct position
    return i;
}

When to use: Arrays (cache-friendly), when average O(n log n) is acceptable, in-place sorting. Java's Arrays.sort() uses dual-pivot QuickSort for primitives.

3. Counting Sort (Non-Comparison)

When values are in a known small range. O(n+k) time.

java
int[] countingSort(int[] arr, int maxVal) {
    int[] count = new int[maxVal + 1];
    for (int num : arr) count[num]++;

    int idx = 0;
    for (int val = 0; val <= maxVal; val++) {
        while (count[val]-- > 0) {
            arr[idx++] = val;
        }
    }
    return arr;
}

When to use: Values are bounded integers in a small range (e.g., ages 0-150, characters a-z).

---

Quick Select (Kth Element in O(n) Average)

Partition-based selection. Like QuickSort but only recurse into the half containing the Kth element.

java
int quickSelect(int[] nums, int left, int right, int k) {
    int pivotIdx = partition(nums, left, right);

    if (pivotIdx == k)      return nums[k];
    else if (pivotIdx < k)  return quickSelect(nums, pivotIdx + 1, right, k);
    else                    return quickSelect(nums, left, pivotIdx - 1, k);
}

// For "Kth largest": k = nums.length - k

Time: O(n) average, O(n²) worst. Randomizing the pivot avoids worst case in practice.

---

Java Sorting APIs

java
// Primitives: Dual-Pivot QuickSort (not stable)
int[] arr = {5, 3, 1, 4, 2};
Arrays.sort(arr);

// Objects: TimSort (stable, O(n log n))
Integer[] arr = {5, 3, 1, 4, 2};
Arrays.sort(arr);

// Custom comparator
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);             // Sort by first element
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0])); // Same, safer (no overflow)

// Collections
List<int[]> list = ...;
list.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]); // Sort by first, then second

// TreeMap / TreeSet: Always sorted (Red-Black Tree, O(log n) operations)
TreeMap<Integer, String> map = new TreeMap<>();

Comparator Overflow Trap

java
// DANGEROUS with large numbers:
(a, b) -> a - b   // Integer overflow if a=Integer.MAX_VALUE, b=-1

// SAFE:
(a, b) -> Integer.compare(a, b)
Comparator.comparingInt(a -> a[0])

---

Interview Applications

Problems

• 148. Sort List - Medium (merge sort on LL)
• 215. Kth Largest Element - Medium (quick select)
• 179. Largest Number - Medium (custom comparator)
• 274. H-Index - Medium (counting sort)
• 315. Count of Smaller Numbers After Self - Hard (merge sort)