Fast sort (merge / quick)

O(n log n)

Sort in O(n log n) by dividing and conquering: merge sort splits then merges two sorted halves, quicksort partitions around a pivot then recurses on each side.

Signals

sort an array of real size (thousands+)need O(n log n) guaranteed or expectedsort 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

Template

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

Looks similar, isn't

Elementary sorts: For real n (thousands or more) an O(n^2) pass is too slow. Elementary sorts only make sense for tiny or nearly-sorted input; otherwise reach for merge or quicksort.
Non-comparison sort (counting/radix): If the keys are small-range integers, counting or radix sort beats O(n log n) by never comparing elements at all. Comparison sort is the default only when the key range isn't small and known.

n up to ~1e5..1e6, arbitrary comparable elements -> O(n log n) time. n large plus no small-integer-key hint is what points here over an O(n^2) or non-comparison sort.

Learn this pattern