Fast sort (merge / quick)

How does Fast sort (merge / quick) work?

Both sorts cut one problem into two smaller ones. They differ in where the cut falls.

Merge sort cuts at the midpoint, without looking at any value. Each half is then sorted the same way.

Merging two sorted halves is one linear pass. Take whichever front element is smaller.

Quick sort picks a pivot value and partitions around it. Smaller values go left, larger ones go right.

After a partition the pivot sits in its final slot. Each side is then sorted on its own.

Both do log n levels of work over n elements. A bad pivot makes quick sort O(n squared).

1. [3, 1, 4, 2]Merge sort. Cut at the midpoint, ignoring the values.
2. [3, 1] and [4, 2]Each half is cut again, down to single elements.
3. [1, 3] and [2, 4]A single element is already sorted. Each pair merges in one comparison.
4. [1, 2, ...]The merge compares the two fronts. 1 is smaller than 2, so it goes first.
5. [1, 2, 3, 4]The last merge is one pass over four elements. Two levels in total.

function mergeSort(arr) {
    if (arr.length <= 1) return arr;
    const mid = arr.length >> 1;
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));
    const out = [];
    let i = 0, j = 0;
    while (i < left.length && j < right.length) {
        out.push(left[i] <= right[j] ? left[i++] : right[j++]);
    }
    return out.concat(left.slice(i), right.slice(j));
}

A worked example of Fast sort (merge / quick)

The kth largest value

Return the kth largest value in an unsorted array.

Sorting the whole array works, but it does far more than the question asked.

Partition around a pivot, exactly as quick sort does.

The pivot then sits in its final slot. Only the side that contains position k needs another round.

function findKthLargest(nums, k) {
    const target = nums.length - k; // the slot it would hold once sorted
    let lo = 0;
    let hi = nums.length - 1;

    while (lo < hi) {
        const pivot = nums[hi];
        let split = lo;

        for (let i = lo; i < hi; i++) {
            if (nums[i] < pivot) {
                [nums[i], nums[split]] = [nums[split], nums[i]];
                split++;
            }
        }
        [nums[split], nums[hi]] = [nums[hi], nums[split]];

        // the pivot is final, and only one side can hold the answer
        if (split === target) return nums[split];
        if (split < target) lo = split + 1;
        else hi = split - 1;
    }

    return nums[lo];
}

When should you use Fast sort (merge / quick)?

These phrases in a problem statement point here:

• •sort an array of real size (thousands+)
• •need O(n log n) guaranteed or expected
• •sort as a subroutine before another algorithm (two pointers, greedy, sweep)
• •stability required (merge sort) or in-place expected (quicksort)
• •just "sort this" with no small-n or special-key hint

What is Fast sort (merge / quick) confused with?

• Elementary sorts (selection, bubble, insertion): Those never split the array and cost n squared. Splitting is what buys the log n.
• Non-comparison sort (counting / radix): Counting and radix sort beat n log n by reading digits. They need keys in a small range.
• Binary heap / priority queue: Heap sort also runs in n log n and needs no buffer. It is slower in practice on real data.
• Recursion: Recursion is the mechanism these use, not the pattern. Where the cut goes is the real idea.

Common mistakes with Fast sort (merge / quick)

• Always taking the first element as pivot

  Sorted input then splits into one and n minus one. Pick a random or middle element.

• Breaking ties toward the right half

  Taking the right element on a tie reorders equal keys. Prefer the left half when they match.

• Recursing on both sides of a quickselect

  Only one side can hold the position you want. Visiting both costs a full sort.

• Forgetting merge sort's buffer

  It allocates a second array the size of the input. On very large arrays that matters.

Which interview problems use Fast sort (merge / quick)?

• Sort an array: The plain form, usually written as merge sort.
• Kth largest element in an array: One partition per round instead of a full sort.
• Merge sorted array: The merge half of merge sort, on its own.
• Count of smaller numbers after self: Counted while the merge step runs.
• Reverse pairs: The same counting trick with a different comparison.
• Sort list: Merge sort over linked nodes, with no buffer.
• Wiggle sort II: Quickselect finds the median, then values are placed around it.

What is the time and space complexity of Fast sort (merge / quick)?

O(n log n)

n up to 1e6 gives O(n log n). Merge sort needs O(n) extra memory, quick sort needs O(log n).