Quick Sort, and When to Just Use .sort()

Do the work while splitting

Merge sort splits the array without looking at the values, and it does all its work when merging.Quick sort is a sorting algorithm that does the opposite. It picks one value, called the pivot. Then it rearranges the array so that everything smaller than the pivot is on its left and everything else is on its right. Now the pivot is exactly where it belongs in the sorted result. The two sides can then be sorted separately, and no merging is needed afterwards.

Partitioning around a pivot

This rearranging step is called partitioning. Partitioning splits an array into a small side and a big side around the pivot. It is done in place (inside the same array), in one pass. Keep a boundary i. Everything before it is smaller than the pivot. Walk through the array. Each time you find a smaller item, swap it to position i and move the boundary one place right. At the end, swap the pivot itself into position i.

Traced: partition([7, 2, 9, 4, 5])

1function partition(arr, lo, hi) {▶  const pivot = arr[hi];3  let i = lo;4  for (let j = lo; j < hi; j++) {5    if (arr[j] < pivot) {6      [arr[i], arr[j]] = [arr[j], arr[i]];7      i++;8    }9  }10  [arr[i], arr[hi]] = [arr[hi], arr[i]];11  return i;12}13const arr = [7, 2, 9, 4, 5];14console.log(partition(arr, 0, 4), arr);

Partitioning is O(n) time and O(1) space. It is also useful on its own. A three-way version sorts an array of 0s, 1s and 2s in one pass (Lesson 21).

Quick sort

Partition the array. Then quick sort the left side and the right side, using recursion. The pivot never moves again.

function quickSort(arr, lo = 0, hi = arr.length - 1) {  if (lo >= hi) return arr;              // 0 or 1 items: already sorted  const p = partition(arr, lo, hi);      // pivot is now at index p, in its final place  quickSort(arr, lo, p - 1);             // sort the smaller side  quickSort(arr, p + 1, hi);             // sort the larger side  return arr;}function partition(arr, lo, hi) {  const r = lo + Math.floor(Math.random() * (hi - lo + 1));   // random pivot  [arr[r], arr[hi]] = [arr[hi], arr[r]];  const pivot = arr[hi];  let i = lo;  for (let j = lo; j < hi; j++) {    if (arr[j] < pivot) {      [arr[i], arr[j]] = [arr[j], arr[i]];      i++;    }  }  [arr[i], arr[hi]] = [arr[hi], arr[i]];  return i;}console.log(quickSort([7, 2, 9, 4, 5, 1, 8])); // [ 1, 2, 4, 5, 7, 8, 9 ]

If each pivot lands near the middle, the array halves at every level, like merge sort. That gives log n levels with O(n) partitioning work on each, so the time is O(n log n). Unlike merge sort, quick sort needs no extra array. It needs only the recursion stack (Lesson 14), which is O(log n) on average. It is not stable, because swaps over a long distance can change the order of equal items.

The worst case, and how to avoid it

Suppose the array is already sorted and the pivot is always the last item. Then the pivot is the largest value every time. One side gets n − 1 items, and the other side gets none.

The fix is simple: choose the pivot at random, as in the code above. Then no particular input can force bad pivots every time. The expected time (the average over the random choices) is O(n log n) for every input. Many libraries instead use the median (the middle value) of the first, middle and last items.

Quickselect: the k-th element without sorting

Quickselect is an algorithm that finds the k-th smallest value without sorting the whole array. After one partition, the pivot is at its final index p. If p is the index you want, you are done. If not, the answer is on one side only. So continue with that side and ignore the other. (The code below uses a loop instead of recursion.)

function kthSmallest(arr, k) {          // k = 1 means the smallest  let lo = 0, hi = arr.length - 1;  const target = k - 1;                    // its index in sorted order  while (true) {    const p = partition(arr, lo, hi);    if (p === target) return arr[p];    if (p < target) lo = p + 1;           // answer is on the right side    else hi = p - 1;                       // answer is on the left side  }}function partition(arr, lo, hi) {  const r = lo + Math.floor(Math.random() * (hi - lo + 1));  [arr[r], arr[hi]] = [arr[hi], arr[r]];  const pivot = arr[hi];  let i = lo;  for (let j = lo; j < hi; j++) {    if (arr[j] < pivot) {      [arr[i], arr[j]] = [arr[j], arr[i]];      i++;    }  }  [arr[i], arr[hi]] = [arr[hi], arr[i]];  return i;}console.log(kthSmallest([7, 2, 9, 4, 5], 2)); // 4

On average, each step keeps about half of the remaining items. The total work is n + n/2 + n/4 + … ≈ 2n. So quickselect is O(n) on average, compared with O(n log n) for sorting first. (In the rare worst case it is O(n²), like quick sort.) It is the classic answer to “k-th largest element”, because the k-th largest is the (n − k + 1)-th smallest.

JavaScript's .sort(): the text-order trap

If you call sort with no arguments, it converts every item to a string(text) and sorts in alphabet order. For numbers this is almost never what you want:

console.log([10, 9, 1, 100].sort());                 // [ 1, 10, 100, 9 ]   ← text order!console.log([10, 9, 1, 100].sort((a, b) => a - b));  // [ 1, 9, 10, 100 ]console.log([10, 9, 1, 100].sort((a, b) => b - a));  // [ 100, 10, 9, 1 ]

As text, “100” comes before “9”, because the first character “1” comes before “9”. Always pass a comparator when you sort numbers. This bug passes small tests (single digits sort correctly as text) and fails on larger values. It is one of the most common JavaScript interview mistakes.

Comparators: numbers, text and objects

A comparator is a function that you give to sort to tell it how to order two items, a and b. It returns a negative number if a should come first, a positive number if b should come first, and 0 if they are equal for sorting. a - b does exactly that for numbers in ascending order (smallest first).

const people = [  { name: "Ravi", age: 30 },  { name: "Lena", age: 25 },  { name: "Omar", age: 30 },];// By one keypeople.sort((a, b) => a.age - b.age);// By textpeople.sort((a, b) => a.name.localeCompare(b.name));// By two keys: age descending, then name ascending for tiespeople.sort((a, b) => b.age - a.age || a.name.localeCompare(b.name));console.log(people.map((p) => p.name)); // [ 'Omar', 'Ravi', 'Lena' ]// sort() changes the array itself. toSorted() returns a sorted copy instead// (toSorted needs Node.js 20 or newer):const nums = [3, 1, 2];const sorted = nums.toSorted((a, b) => a - b);console.log(nums, sorted);               // [ 3, 1, 2 ] [ 1, 2, 3 ]

• Two keys: first || second works because a 0 from the first comparison (a tie) is treated as “false”, so JavaScript uses the second comparison instead.
• Never return a boolean such as a > b. It gives only true or false (which become 1 or 0). It never gives a negative number, so the order can be wrong.
• Cost: sort is O(n log n) and stable. Count it in your Big-O.

Which sort to use

Practice questions

Several of these are about writing the right comparator. You will use this skill in almost every later part.

function findKthLargest(nums, k) {  return [...nums].sort((a, b) => b - a)[k - 1];}console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2));          // 5console.log(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)); // 4

function findKthLargest(nums, k) {  const a = [...nums];  const target = a.length - k;  let lo = 0, hi = a.length - 1;  while (true) {    const r = lo + Math.floor(Math.random() * (hi - lo + 1));    [a[r], a[hi]] = [a[hi], a[r]];    const pivot = a[hi];    let i = lo;    for (let j = lo; j < hi; j++) {      if (a[j] < pivot) { [a[i], a[j]] = [a[j], a[i]]; i++; }    }    [a[i], a[hi]] = [a[hi], a[i]];    if (i === target) return a[i];    if (i < target) lo = i + 1;    else hi = i - 1;  }}console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2));          // 5console.log(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)); // 4

function sortColors(nums) {  const count = [0, 0, 0];  for (const x of nums) count[x]++;  let i = 0;  for (let v = 0; v < 3; v++) {    for (let c = 0; c < count[v]; c++) nums[i++] = v;  }  return nums;}console.log(sortColors([2, 0, 2, 1, 1, 0])); // [ 0, 0, 1, 1, 2, 2 ]

function sortColors(nums) {  let low = 0, mid = 0, high = nums.length - 1;  while (mid <= high) {    if (nums[mid] === 0) {      [nums[low], nums[mid]] = [nums[mid], nums[low]];      low++; mid++;    } else if (nums[mid] === 1) {      mid++;    } else {      [nums[mid], nums[high]] = [nums[high], nums[mid]];      high--;    }  }  return nums;}console.log(sortColors([2, 0, 2, 1, 1, 0])); // [ 0, 0, 1, 1, 2, 2 ]console.log(sortColors([2, 0, 1]));          // [ 0, 1, 2 ]

function frequencySort(nums) {  const freq = new Map();  for (const x of nums) freq.set(x, (freq.get(x) ?? 0) + 1);  return nums.sort((a, b) => freq.get(a) - freq.get(b) || b - a);}console.log(frequencySort([1, 1, 2, 2, 2, 3])); // [ 3, 1, 1, 2, 2, 2 ]console.log(frequencySort([2, 3, 1, 3, 2]));    // [ 1, 3, 3, 2, 2 ]

function sortPeople(names, heights) {  return names    .map((_, i) => i)    .sort((a, b) => heights[b] - heights[a])    .map((i) => names[i]);}console.log(sortPeople(["Mary", "John", "Emma"], [180, 165, 170])); // [ 'Mary', 'Emma', 'John' ]

function sortPeople(names, heights) {  return names    .map((name, i) => [heights[i], name])    .sort((a, b) => b[0] - a[0])    .map(([, name]) => name);}console.log(sortPeople(["Mary", "John", "Emma"], [180, 165, 170])); // [ 'Mary', 'Emma', 'John' ]

function largestNumber(nums) {  const s = nums    .map(String)    .sort((a, b) => (b + a).localeCompare(a + b))    .join("");  return s[0] === "0" ? "0" : s;}console.log(largestNumber([10, 2]));           // 210console.log(largestNumber([3, 30, 34, 5, 9])); // 9534330console.log(largestNumber([0, 0]));            // 0

function pivotArray(nums, pivot) {  const less = [], equal = [], greater = [];  for (const x of nums) {    if (x < pivot) less.push(x);    else if (x === pivot) equal.push(x);    else greater.push(x);  }  return [...less, ...equal, ...greater];}console.log(pivotArray([9, 12, 5, 10, 14, 3, 10], 10)); // [ 9, 5, 3, 10, 10, 12, 14 ]

function sortArray(nums) {  function sort(lo, hi) {    if (lo >= hi) return;    const pivot = nums[lo + Math.floor(Math.random() * (hi - lo + 1))];    let lt = lo, i = lo, gt = hi;    while (i <= gt) {      if (nums[i] < pivot) { [nums[lt], nums[i]] = [nums[i], nums[lt]]; lt++; i++; }      else if (nums[i] > pivot) { [nums[i], nums[gt]] = [nums[gt], nums[i]]; gt--; }      else i++;    }    sort(lo, lt - 1);       // values < pivot    sort(gt + 1, hi);       // values > pivot  }  sort(0, nums.length - 1);  return nums;}console.log(sortArray([5, 2, 3, 1]));             // [ 1, 2, 3, 5 ]console.log(sortArray([5, 1, 1, 2, 0, 0]));       // [ 0, 0, 1, 1, 2, 5 ]console.log(sortArray(new Array(8).fill(7)));     // [ 7, 7, 7, 7, 7, 7, 7, 7 ]

Make it stick

Part 3 complete — what's next

You now know what sorting does, how the O(n log n) sorts work, and how to sort anything correctly in JavaScript. Sorting will often appear as the first step of later solutions.

Part 4 — Arrays and the First Patterns begins with the array problems that open almost every coding round. These are: finding the largest and second largest values, removing duplicates in place, rotating an array, and finding missing numbers.