SyntaxPilot
Courses/JavaScript/Lesson 37
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

JavaScript · Lesson 37 of 40

DSA in JS 4: sorting and searching

queued

These are the notes for JavaScript episode 37, part four of data structures and algorithms. Ravi's "cheapest first" button shows 1200 before 7, so we learn how sort really compares, sort names with localeCompare, and keep the original list safe with toSorted. Then we invent sorting ourselves: bubble sort works but needs about 200 million comparisons for 20,000 answer sheets, so we invent merge sort (about 264,000). Finally we search a million phone numbers: linear search needs a million steps, binary search needs 20, but only on sorted data. Every output below is real Node.js output (Node 24). Times vary from machine to machine; the comparison counts do not.

Builds on: arrays and array methods (episode 7), functions and arrow functions (9), map/filter/reduce (11), destructuring and spread (12), Big O (34), recursion and binary search trees (36). Leads to: DSA in JavaScript 5: dynamic programming (38).

Ravi's price list: the sort trap

Ravi's shop app shows five prices. Customers want a "cheapest first" button.

const prices = [500, 40, 1200, 99, 7];
prices.sort();
console.log(prices);

Output:

[ 1200, 40, 500, 7, 99 ]

Why it's wrong: with no compare function, sort converts every item to a string and compares the strings character by character (by their UTF-16 code units), like words in a dictionary. "1200" starts with "1", and "1" comes before "4", "5", "7" and "9", so 1200 comes first.

Compare functions

Pass sort a compare function (a, b) => .... It answers "which of a and b goes first?":

The function returns Meaning
a negative number a goes before b
a positive number b goes before a
0 keep their current order

For numbers, a - b does exactly this: 40 - 500 = -460, so 40 goes first.

const prices = [500, 40, 1200, 99, 7];
prices.sort((a, b) => a - b);
console.log("low to high:", prices);
prices.sort((a, b) => b - a);
console.log("high to low:", prices);

Output:

low to high: [ 7, 40, 99, 500, 1200 ]
high to low: [ 1200, 500, 99, 40, 7 ]

Remember: a - b = ascending (low to high), b - a = descending (high to low).

Sorting names: localeCompare

const names = ["Ravi", "aman", "Zara", "Neha", "isha"];
console.log([...names].sort());
console.log([...names].sort((a, b) => a.localeCompare(b)));

Output:

[ 'Neha', 'Ravi', 'Zara', 'aman', 'isha' ]
[ 'aman', 'isha', 'Neha', 'Ravi', 'Zara' ]

The default sort compares character codes, and every capital letter (A = 65 … Z = 90) has a smaller code than every small letter (a = 97). So "Zara" comes before "aman". a.localeCompare(b) compares the way people read, following the language's rules, and returns a negative number, a positive number or 0, exactly what sort wants.

[...names] makes a copy first (spread, episode 12), so both lines start from the same list.

sort changes the array: toSorted

const prices = [500, 40, 1200, 99, 7];
const cheapFirst = prices.sort((a, b) => a - b);
console.log("cheapFirst:", cheapFirst);
console.log("prices:    ", prices);

Output:

cheapFirst: [ 7, 40, 99, 500, 1200 ]
prices:     [ 7, 40, 99, 500, 1200 ]

sort works in place: it rearranges the array itself and returns the same array. cheapFirst is not a copy; it is a second name for the same list. A method that changes the original like this mutates it.

const prices = [500, 40, 1200, 99, 7];
const cheapFirst = prices.toSorted((a, b) => a - b);
console.log("cheapFirst:", cheapFirst);
console.log("prices:    ", prices);

Output:

cheapFirst: [ 7, 40, 99, 500, 1200 ]
prices:     [ 500, 40, 1200, 99, 7 ]

toSorted (ES2023, Node 20+) returns a new sorted array. In older code you'll see [...prices].sort(...), which does the same. The same family: toReversed, toSpliced, with (episode 29).

Inventing sorting: bubble sort

The teacher's answer sheets: compare two neighbouring sheets; if the bigger one is first, swap them; move one step along. After one pass, the biggest mark has "bubbled" to the end. Repeat for the rest of the pile.

function bubbleSort(arr) {
  let comparisons = 0;
  for (let end = arr.length - 1; end > 0; end--) {
    for (let i = 0; i < end; i++) {
      comparisons++;
      if (arr[i] > arr[i + 1]) [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
    }
  }
  return comparisons;
}
const marks = [72, 35, 90, 58, 41];
console.log("comparisons:", bubbleSort(marks));
console.log(marks);

Output:

comparisons: 10
[ 35, 41, 58, 72, 90 ]
  • end marks where the unsorted part ends; after each pass, one more sheet is in its final place.
  • [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]] swaps two values with destructuring (episode 12).

Why bubble sort is slow

// bubbleSort as above
for (const n of [10, 1000, 20000]) {
  const marks = Array.from({ length: n }, (_, i) => (i * 7919) % 101);
  console.time(`${n} sheets`);
  const c = bubbleSort(marks);
  console.timeEnd(`${n} sheets`);
  console.log("  comparisons:", c.toLocaleString("en-US"));
}

Output (times vary):

10 sheets: 0.068ms
  comparisons: 45
1000 sheets: 15.255ms
  comparisons: 499,500
20000 sheets: 2.795s
  comparisons: 199,990,000

Bubble sort always makes n(n − 1) / 2 comparisons: one pass per sheet, each pass across the pile. That is O(n²): 20 times more sheets means about 400 times more work. (i * 7919) % 101 just makes repeatable, mixed-up marks from 0 to 100. console.time / console.timeEnd print how long the code between them took.

Merge sort: split, sort, merge

Two teachers, one trick: split the pile in half, each teacher sorts a half (by splitting again, until single sheets, which are already sorted), then merge the two sorted piles: look at the top sheet of each pile, take the smaller one, repeat.

let comparisons = 0;
function merge(left, right) {
  const out = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    comparisons++;
    if (left[i] <= right[j]) out.push(left[i++]);
    else out.push(right[j++]);
  }
  return [...out, ...left.slice(i), ...right.slice(j)];
}
console.log(merge([35, 58, 90], [41, 72]));

Output:

[ 35, 41, 58, 72, 90 ]
// comparisons and merge as above
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  return merge(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid)));
}
console.log(mergeSort([72, 35, 90, 58, 41]));
const marks = Array.from({ length: 20000 }, (_, i) => (i * 7919) % 101);
comparisons = 0;
console.time("mergeSort 20000");
const sorted = mergeSort(marks);
console.timeEnd("mergeSort 20000");
console.log("  comparisons:", comparisons.toLocaleString("en-US"));

Output (times vary):

[ 35, 41, 58, 72, 90 ]
mergeSort 20000: 34.75ms
  comparisons: 263,876
Bubble sort Merge sort
idea swap neighbours split, sort halves, merge
comparisons for 20,000 199,990,000 263,876
time complexity O(n²) O(n log n)
extra memory O(1), in place O(n), new arrays
stable? yes yes (<= takes the left item on ties)

Why n log n: 20,000 halves about 15 times before the piles are single sheets (2¹⁵ ≈ 32,768), and each level of merging touches every sheet once: about 20,000 × 15 = 300,000 steps.

JavaScript's own sort (in V8, the engine inside Node and Chrome) uses TimSort, a merge sort that also spots runs that are already in order. It is O(n log n) and stable. In real code, use sort/toSorted with a compare function; write your own only to learn or for special cases.

Sorting objects, and stability

const students = [
  { name: "Aman", marks: 72 }, { name: "Isha", marks: 90 },
  { name: "Ravi", marks: 72 }, { name: "Neha", marks: 58 },
  { name: "Zara", marks: 90 },
];
const ranked = students.toSorted((a, b) => b.marks - a.marks);
for (const s of ranked) console.log(s.marks, s.name);

Output:

90 Isha
90 Zara
72 Aman
72 Ravi
58 Neha

Tied students kept their original order (Isha before Zara, Aman before Ravi). A sort that keeps equal items in their original order is stable. Since ES2019, Array.prototype.sort must be stable, so you can sort by a second key first and then by the main key, or combine keys in one compare function: b.marks - a.marks || a.name.localeCompare(b.name) (if the marks difference is 0, || falls through to the names).

const phones = Array.from({ length: 1000000 }, (_, i) => 9000000000 + i * 3);
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return { index: i, steps: i + 1 };
  }
  return { index: -1, steps: arr.length };
}
console.log(linearSearch(phones, 9000000000));
console.log(linearSearch(phones, 9002999997));
console.log(linearSearch(phones, 9000000001));

Output:

{ index: 0, steps: 1 }
{ index: 999999, steps: 1000000 }
{ index: -1, steps: 1000000 }

Linear search checks items one by one: O(n). A missing item always costs the full n steps. indexOf, includes, find and findIndex are all linear searches.

Binary search: the dictionary trick

Open a dictionary in the middle; if your word comes later, throw away the first half; repeat. Each look halves what is left.

function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1, steps = 0;
  while (lo <= hi) {
    steps++;
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] === target) return { index: mid, steps };
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return { index: -1, steps };
}
const phones = Array.from({ length: 1000000 }, (_, i) => 9000000000 + i * 3);
console.log(binarySearch(phones, 9000000000));
console.log(binarySearch(phones, 9002999997));
console.log(binarySearch(phones, 9000000001));

Output:

{ index: 0, steps: 19 }
{ index: 999999, steps: 20 }
{ index: -1, steps: 20 }
  • lo and hi mark the part of the array where the target could still be.
  • If the middle is smaller than the target, the target is to the right: lo = mid + 1; otherwise hi = mid - 1.
  • When lo > hi, the range is empty: not found.
  • 2²⁰ ≈ 1,048,576, so a million items need at most 20 looks: O(log n).

The one rule: sorted data only

// binarySearch as above
const prices = [500, 40, 1200, 99, 7];
console.log(prices.indexOf(40));
console.log(binarySearch(prices, 40));
console.log(binarySearch(prices.toSorted((a, b) => a - b), 40));

Output:

1
{ index: -1, steps: 2 }
{ index: 1, steps: 3 }

On the unsorted list, the middle is 1200; 40 is smaller, so binary search goes left (to 500, then gives up), but 40 was at index 1 all along. No error, just a wrong answer. Binary search is only correct on sorted data. Sorting costs O(n log n) once; after that every search is O(log n), so "sort once, search many times" wins when you search often. (The index returned is the index in the sorted copy.)

Which one when?

Task Use Cost
sort numbers toSorted((a, b) => a - b) O(n log n)
sort words / names toSorted((a, b) => a.localeCompare(b)) O(n log n)
find once in unsorted data indexOf / find O(n)
find many times sort once, then binary search (or a Set/Map, episode 21) O(log n) each (O(1) for Set/Map)
tiny arrays (under ~10) anything it doesn't matter

Common mistakes (and what really happens)

Mistake What you see Why Fix
[500, 40, 1200].sort() [ 1200, 40, 500 ] default sort compares strings sort((a, b) => a - b)
names.sort() with mixed case [ 'Neha', 'Ravi', 'Zara', 'aman', 'isha' ] capitals have smaller character codes a.localeCompare(b)
const copy = prices.sort(...) prices changed too sort mutates and returns the same array toSorted, or [...prices].sort(...)
a compare function returning true/false: (a, b) => a > b unreliable order sort needs negative / positive / 0, and false counts as 0 (a, b) => a - b
bubble sort on big data 199,990,000 comparisons, seconds O(n²) built-in sort / merge sort, O(n log n)
binary search on unsorted data { index: -1, steps: 2 } although 40 is there "smaller" no longer means "to the left" sort first
while (lo < hi) with hi = arr.length - 1 the last remaining item is never checked the loop stops one step early while (lo <= hi) (or the [lo, hi) style in practice 3)

Mini project: the class leaderboard

Rank students by marks (highest first), ties in name order, then use binary search to find which rank a new score would get.

const students = [
  { name: "Zara", marks: 90 }, { name: "Aman", marks: 72 },
  { name: "Isha", marks: 90 }, { name: "Ravi", marks: 72 },
  { name: "Neha", marks: 58 }, { name: "Kiran", marks: 81 },
];
const board = students
  .toSorted((a, b) => a.name.localeCompare(b.name))
  .toSorted((a, b) => b.marks - a.marks);
board.forEach((s, i) => console.log(`${i + 1}. ${s.name.padEnd(6)} ${s.marks}`));

// rank of a new score: how many scored strictly more? (binary search on descending marks)
function rankFor(score) {
  let lo = 0, hi = board.length;
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (board[mid].marks > score) lo = mid + 1;
    else hi = mid;
  }
  return lo + 1;
}
console.log("a score of 85 would be rank", rankFor(85));
console.log("a score of 72 would be rank", rankFor(72));
console.log("a score of 40 would be rank", rankFor(40));

Output:

1. Isha   90
2. Zara   90
3. Kiran  81
4. Aman   72
5. Ravi   72
6. Neha   58
a score of 85 would be rank 3
a score of 72 would be rank 4
a score of 40 would be rank 7

Sorting by name first and then by marks works because the sort is stable: students with equal marks stay in name order.

Practice

1. Sort Ravi's items by price, and by name when prices are equal.

Solution
const items = [
  { name: "Soap", price: 40 }, { name: "Biscuits", price: 30 },
  { name: "Atta", price: 300 }, { name: "Bread", price: 40 },
  { name: "Chai patti", price: 120 },
];
const sorted = items.toSorted((a, b) => a.price - b.price || a.name.localeCompare(b.name));
for (const it of sorted) console.log(it.price, it.name);

Output:

30 Biscuits
40 Bread
40 Soap
120 Chai patti
300 Atta

a.price - b.price is 0 for Bread and Soap, so || uses localeCompare.

2. Write insertion sort (the way you arrange playing cards in your hand) and count its comparisons.

Solution
function insertionSort(arr) {
  let comparisons = 0;
  for (let i = 1; i < arr.length; i++) {
    const card = arr[i];
    let j = i - 1;
    while (j >= 0) {
      comparisons++;
      if (arr[j] <= card) break;
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = card;
  }
  return comparisons;
}
const marks = [72, 35, 90, 58, 41];
console.log("comparisons:", insertionSort(marks), marks);
const nearly = [1, 2, 3, 5, 4, 6, 7, 8, 9, 10];
console.log("nearly sorted:", insertionSort(nearly), "comparisons");

Output:

comparisons: 9 [ 35, 41, 58, 72, 90 ]
nearly sorted: 10 comparisons

Insertion sort is O(n²) in the worst case but close to O(n) on nearly sorted data (10 comparisons for 10 items here, bubble sort above would always do 45). TimSort uses insertion sort for small pieces for exactly this reason.

3. Write firstAtLeast(arr, x): the first index where arr[i] >= x in a sorted array (or arr.length if none).

Solution
function firstAtLeast(arr, x) {
  let lo = 0, hi = arr.length;
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] < x) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}
const prices = [7, 40, 40, 99, 500, 1200];
console.log(firstAtLeast(prices, 40));
console.log(firstAtLeast(prices, 100));
console.log(firstAtLeast(prices, 5000));

Output:

1
4
6

Here hi starts at arr.length and the range is [lo, hi) (hi excluded), so the loop is while (lo < hi) and hi = mid. This is called a lower bound. With duplicates (two 40s) it returns the first one.

4. Count how many values lie between low and high (inclusive) in a sorted array, in O(log n).

Solution
// firstAtLeast as above
function countBetween(arr, low, high) {
  return firstAtLeast(arr, high + 1) - firstAtLeast(arr, low);
}
console.log(countBetween(prices, 40, 500));
const phones = Array.from({ length: 1000000 }, (_, i) => 9000000000 + i * 3);
console.log(countBetween(phones, 9000000000, 9000000299));

Output:

4
100

(For whole numbers, "first index at least high + 1" is the end of the range.) Two binary searches, about 40 steps, instead of a million.

Quick quiz

const a = [10, 9, 1, 100];
const b = a.sort();
b.push(5);
console.log(a);

A. [ 1, 9, 10, 100 ] B. [ 1, 10, 100, 9, 5 ] C. [ 1, 10, 100, 9 ] D. [ 10, 9, 1, 100, 5 ]

Answer

B: [ 1, 10, 100, 9, 5 ]. Without a compare function the order is by text: "1" < "10" < "100" < "9". sort returns the same array, so b is a, and b.push(5) changes a too. Node really prints [ 1, 10, 100, 9, 5 ].

Interview questions

  1. Why does [10, 9, 1].sort() give [1, 10, 9]? Without a compare function, sort converts items to strings and compares them by UTF-16 code units.
  2. What must a compare function return? A negative number (a first), a positive number (b first) or 0 (keep order). Returning a boolean is a bug.
  3. What is the difference between sort and toSorted? sort sorts in place and returns the same array; toSorted returns a new sorted array and leaves the original unchanged.
  4. What is a stable sort, and is JavaScript's sort stable? Equal items keep their original relative order. Yes, required since ES2019.
  5. Time complexity of bubble, insertion, merge and quick sort? Bubble and insertion O(n²) (insertion O(n) on nearly sorted data); merge sort O(n log n) always, O(n) extra memory; quicksort O(n log n) on average, O(n²) worst case, in place.
  6. What algorithm does V8 use for Array.prototype.sort? TimSort: a hybrid of merge sort and insertion sort, O(n log n), stable.
  7. What is the precondition of binary search, and its complexity? The data must be sorted; O(log n) time, O(1) memory (iterative).
  8. How would you find the first and last position of a value in a sorted array? Two lower-bound binary searches: firstAtLeast(x) and firstAtLeast(x + 1) - 1 (for whole numbers).
  9. When is linear search better than binary search? When the data is unsorted and you search only once (sorting would cost more), or the array is tiny.

Glossary

Term Meaning Example
sorting arranging items in order prices low to high
ascending / descending low to high / high to low a - b / b - a
compare function tells sort which of two items goes first (a, b) => a - b
default sort order items compared as strings [1200, 40, 500, 7, 99]
character code (UTF-16 code unit) the number behind each character "A" = 65, "a" = 97
localeCompare compares strings the way people read "aman".localeCompare("Zara") < 0
in place changes the original array sort, reverse
mutate change an existing value prices.sort()
toSorted returns a sorted copy (ES2023) prices.toSorted((a, b) => a - b)
swap exchange two values [a, b] = [b, a]
bubble sort repeatedly swap out-of-order neighbours 10 comparisons for 5 sheets
pass one walk through the array the biggest sheet reaches the end
O(n²) work grows with the square of n 20× data → 400× work
merge combine two sorted lists into one [35, 58, 90] + [41, 72]
merge sort split, sort halves recursively, merge 263,876 comparisons for 20,000
O(n log n) n times the number of halvings the speed of good sorts
TimSort merge sort + insertion sort hybrid used by V8 Array.prototype.sort
insertion sort insert each item into the sorted part on its left arranging cards in your hand
stable sort equal items keep their original order Isha before Zara
console.time / console.timeEnd measure how long code takes 20000 sheets: 2.795s
linear search check items one by one indexOf, O(n)
binary search look in the middle, discard half 20 steps for a million
O(log n) steps grow with the number of halvings 2²⁰ ≈ 1,000,000
lower bound first index with arr[i] >= x firstAtLeast(prices, 40) is 1
precondition what must be true before an algorithm works sorted data for binary search

Summary

  • sort() without a compare function sorts as text: use (a, b) => a - b for numbers and localeCompare for words.
  • sort mutates the array and returns it; toSorted returns a new array.
  • Bubble sort swaps neighbours: simple, but O(n²): 199,990,000 comparisons for 20,000 items.
  • Merge sort splits, sorts halves and merges: O(n log n): 263,876 comparisons. JavaScript's own sort (TimSort) is O(n log n) and stable.
  • Linear search is O(n); binary search is O(log n), 20 steps for a million, but only on sorted data.
  • Next: dynamic programming, when the pieces of a problem repeat and recursion solves the same piece millions of times.