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 ]
endmarks 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).
Searching: linear search
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 }
loandhimark 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; otherwisehi = 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
- Why does
[10, 9, 1].sort()give[1, 10, 9]? Without a compare function,sortconverts items to strings and compares them by UTF-16 code units. - 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.
- What is the difference between
sortandtoSorted?sortsorts in place and returns the same array;toSortedreturns a new sorted array and leaves the original unchanged. - What is a stable sort, and is JavaScript's sort stable? Equal items keep their original relative order. Yes, required since ES2019.
- 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.
- What algorithm does V8 use for
Array.prototype.sort? TimSort: a hybrid of merge sort and insertion sort, O(n log n), stable. - What is the precondition of binary search, and its complexity? The data must be sorted; O(log n) time, O(1) memory (iterative).
- How would you find the first and last position of a value in a sorted array? Two lower-bound binary searches:
firstAtLeast(x)andfirstAtLeast(x + 1) - 1(for whole numbers). - 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 - bfor numbers andlocaleComparefor words.sortmutates the array and returns it;toSortedreturns 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.