Quicksort and Merge Sort: Deep Implementation

Quicksort: Comparing Partitioning Schemes

Lomuto Partitioning (Single pointer)

The logic relies on a slowly moving pointer i that marks the end of the "smaller than pivot" section, while j scans correctly.

int partition(int[] arr, int lo, int hi) {
    int pivot = arr[hi];
    int i = lo; // Points to the index where the next smaller element should go
    for (int j = lo; j < hi; j++) {
        if (arr[j] <= pivot) {
            swap(arr, i++, j); // Swap smaller element to index i, then increment i
        }
    }
    swap(arr, i, hi); // Place the pivot in its final sorted position
    return i;
}

Pros: Simple logic, easy to recall and implement.
Cons: Inefficient with many duplicate elements, as it doesn't balance "equal to pivot" values well.

Hoare Partitioning (Dual-ended scanning)

Scans from both ends simultaneously. It's roughly 3x more efficient in terms of swaps than Lomuto and is the industry standard for production sorts.

int partition(int[] arr, int lo, int hi) {
    int pivot = arr[lo + (hi - lo) / 2]; // Midpoint pivot
    int i = lo - 1, j = hi + 1;
    while (true) {
        // Find leftmost element >= pivot
        do { i++; } while (arr[i] < pivot);
        // Find rightmost element <= pivot
        do { j--; } while (arr[j] > pivot);
        
        if (i >= j) return j; // Pointers crossed, partitioning complete
        swap(arr, i, j);
    }
}

// Note: Hoare partition returns j. Sorting calls should be:
void quickSort(int[] arr, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(arr, lo, hi);
    quickSort(arr, lo, p);      // Sorts [lo..p]
    quickSort(arr, p + 1, hi);  // Sorts [p+1..hi]
}

3-Way Quicksort: Optimizing for Duplicate Keys (Dutch National Flag)

Standard Quicksort only places one element in its final position per partition. 3-Way Quicksort segments the array into three parts ($<$, $==$, $>$ pivot), placing all equal elements in their final positions simultaneously.

[3, 1, 4, 3, 5, 3, 2, 3]  pivot = 3
Result: [1, 2 | 3, 3, 3, 3 | 4, 5]
        < pivot   == pivot   > pivot

void quickSort3Way(int[] arr, int lo, int hi) {
    if (lo >= hi) return;
    
    int pivot = arr[lo];
    int lt = lo, gt = hi, i = lo + 1;
    
    while (i <= gt) {
        if (arr[i] < pivot) {
            swap(arr, lt++, i++); // Move smaller element to the left region
        } else if (arr[i] > pivot) {
            swap(arr, i, gt--);   // Move larger element to the right region
            // Note: i is NOT incremented because the swapped element from gt must be checked
        } else {
            i++; // Equal to pivot, simply expand the middle region
        }
    }
    
    // Recursive calls on < and > sections ONLY
    quickSort3Way(arr, lo, lt - 1);
    quickSort3Way(arr, gt + 1, hi);
}

Merge Sort Variations

Standard Merge Sort requires $O(N)$ extra space, but implementation details vary.

Optimal Space: Reusing a Global Buffer

Instead of creating new arrays on each recursion, pass a single "temp" array through the calls.

void mergeSort(int[] arr) {
    int[] temp = new int[arr.length];
    sortHelper(arr, temp, 0, arr.length - 1);
}

private void sortHelper(int[] arr, int[] temp, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    sortHelper(arr, temp, lo, mid);
    sortHelper(arr, temp, mid + 1, hi);
    merge(arr, temp, lo, mid, hi);
}

private void merge(int[] arr, int[] temp, int lo, int mid, int hi) {
    // 1. Copy the relevant range to the scratch buffer
    for (int k = lo; k <= hi; k++) temp[k] = arr[k];
    
    // 2. Merge back to the original array
    int i = lo, j = mid + 1;
    for (int k = lo; k <= hi; k++) {
        if (i > mid)               arr[k] = temp[j++];
        else if (j > hi)           arr[k] = temp[i++];
        else if (temp[i] <= temp[j]) arr[k] = temp[i++]; // <= maintains stability
        else                       arr[k] = temp[j++];
    }
}

Bottom-Up Merge Sort (Iterative)

Eliminate recursion to save stack frames and prevent stack overflow on extremely large arrays.

void mergeSortBottomUp(int[] arr) {
    int n = arr.length;
    int[] temp = new int[n];
    for (int size = 1; size < n; size *= 2) { // 1, 2, 4, 8...
        for (int lo = 0; lo < n - size; lo += 2 * size) {
            int mid = lo + size - 1;
            int hi = Math.min(lo + 2 * size - 1, n - 1);
            merge(arr, temp, lo, mid, hi);
        }
    }
}

Advanced Application: Counting Inversions (LeetCode 315)

An inversion occurs when i < j but arr[i] > arr[j]. This metric measures how unsorted an array is. During the merge phase, if an element from the right half (temp[j]) is smaller than an element from the left half (temp[i]), then temp[j] forms an inversion with all remaining elements in the left half.

long inversionCount = 0;

private void merge(int[] arr, int[] temp, int lo, int mid, int hi) {
    for (int k = lo; k <= hi; k++) temp[k] = arr[k];
    int i = lo, j = mid + 1;
    for (int k = lo; k <= hi; k++) {
        if (i > mid) arr[k] = temp[j++];
        else if (j > hi) arr[k] = temp[i++];
        else if (temp[i] <= temp[j]) {
            arr[k] = temp[i++];
        } else {
            // Logic: All elements from current i to mid in the left half are > temp[j]
            inversionCount += (mid - i + 1);
            arr[k] = temp[j++];
        }
    }
}

Sorting a Linked List (LeetCode 148)

Since linked lists do not support random access, Merge Sort is the optimal sorting choice.

public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) return head;
    
    // 1. Find midpoint using Fast/Slow pointers
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode midpoint = slow.next;
    slow.next = null; // Decouple lists
    
    // 2. Recursively sort both halves
    ListNode left = sortList(head);
    ListNode right = sortList(midpoint);
    
    // 3. Merge sorted halves
    return merge(left, right);
}

private ListNode merge(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), current = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) { current.next = l1; l1 = l1.next; }
        else                  { current.next = l2; l2 = l2.next; }
        current = current.next;
    }
    current.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

Complexity & Characteristics Summary

*With randomization, the probability of hitting O(N²) becomes statistically negligible.