Array patterns · Lesson 10 of 23
Sorting: merge sort and quicksort
How sorting works inside, how to use `sort` correctly, and when sorting is the solution.
First thing to know: JavaScript's sort() without a comparator sorts as strings! [10, 9, 1].sort() gives [1, 10, 9]. For numbers always write sort((a, b) => a - b).
The comparator returns a negative number if a goes first, positive if after, and zero if equal.
console.log([10, 9, 1].sort())
console.log([10, 9, 1].sort((a, b) => a - b))
// Sort by several keys: score high to low, then name A to Z
const people = [{ name: "Omar", score: 90 }, { name: "Mona", score: 95 }, { name: "Adam", score: 90 }]
people.sort((a, b) => b.score - a.score || a.name.localeCompare(b.name))
console.log(people.map((p) => p.name))Merge sort: split and merge
function mergeSort(nums) {
if (nums.length <= 1) return nums
const mid = nums.length >> 1
const left = mergeSort(nums.slice(0, mid))
const right = mergeSort(nums.slice(mid))
// Merge two sorted halves: always take the smaller front item
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))
}
console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]))- [38, 27, 43, 3]
- [38, 27]
- [38]
- [27]
- [43, 3]
- [43]
- [3]
- [38, 27]
Splitting makes log n levels and merging each level takes n steps: O(n log n) always, even in the worst case.
Quicksort: pick a pivot and partition
function quickSort(nums, lo = 0, hi = nums.length - 1) {
if (lo >= hi) return nums
const pivot = nums[hi]
let wall = lo // everything before wall is < pivot
for (let i = lo; i < hi; i++) {
if (nums[i] < pivot) { [nums[i], nums[wall]] = [nums[wall], nums[i]]; wall++ }
}
;[nums[wall], nums[hi]] = [nums[hi], nums[wall]] // the pivot lands in its final place
quickSort(nums, lo, wall - 1)
quickSort(nums, wall + 1, hi)
return nums
}
console.log(quickSort([38, 27, 43, 3, 9, 82, 10]))| Algorithm | Average | Worst | Space | Stable? |
|---|---|---|---|---|
Merge sort | O(n log n) | O(n log n) | O(n) | Yes |
Quicksort | O(n log n) | O(n²) | O(log n) | No |
Heap sort | O(n log n) | O(n log n) | O(1) | No |
Insertion sort | O(n²) | O(n²) | O(1) | Yes |
Array.prototype.sort (V8) | O(n log n) | O(n log n) | O(n) | Yes (TimSort) |
What's the output?
console.log([5, 25, 100, 1].sort().join(" "))What will this code print?
Exercise
Sort the students by xp descending, then by name alphabetically, and print the names. It must print Laila Mona Omar.
Expected output: Laila Mona Omar
const students = [{ name: "Omar", xp: 80 }, { name: "Mona", xp: 120 }, { name: "Laila", xp: 120 }]
// sort here
console.log(students.map((s) => s.name).join(" "))Practise on real problems
Practice problems that use what you learned here. Solve them in JavaScript, Python or C++.
Learn more from
Played 0 of 2 games
Sign in to save your progress and earn XP.