Jars of tea in neat rows on blue shelves

Sorting algorithms in JavaScript: see and hear how they work

Why does JavaScript's sort() put 10 before 9, and which sorting algorithm is fastest? See and hear bubble sort, merge sort, quicksort and more at work on an HTML5 canvas, then code them yourself.

The canvas below sorts 48 bars, one algorithm after another. Every bar is a number, and a taller bar is a bigger number. The red bars are the ones the algorithm is comparing or moving right now. Turn on the sound, and every step plays a note: the taller the bar, the higher the note. You can also pick a single algorithm from the list:

Algorithm
Sound

What is a sorting algorithm?

A sorting algorithm puts the items of an array in order, like numbers from smallest to largest or names from A to Z. It only needs two actions to do that: it compares two items, and it moves items to another place. The algorithms on this page differ in which items they compare, and when they move them.

Every array in JavaScript already has a sort() method, so you might wonder why you'd write your own. In most code, you shouldn't, and the section about sort() further down this page shows how to use it well. But the algorithms behind it are worth knowing, for these reasons:

  • Understanding - You'll know why sort() is fast, and what it does with your array.
  • Interviews - Sorting algorithms are a classic topic in coding interviews and computer science classes.
  • Games - A game sorts things all the time, for example its characters, so it can draw them in the right order. Knowing how sorting works helps you keep that sorting fast.

Most algorithms on this page swap two items in an array. Here's a small function that does that, and the code on this page uses it a lot:

function swap(array, i, j) {
    let temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

temp holds on to the item at i, so it isn't lost when the item at j takes its place.

Each algorithm also has its own demo, with 12 bars, each with its value underneath. Red bars are being compared or moved, and green bars are in their final place. Above the bars, the demo counts the comparisons and the moves. Most algorithms move items by swapping them, but insertion sort shifts them and merge sort writes them, so their counters say Shifts and Writes.

The demos play by themselves, unless your device is set to reduce motion. Click Pause to stop one, Step to take one step at a time, and New array to start over with new numbers.

Bubble sort: swap neighbors until nothing moves

Bubble sort is the simplest sorting algorithm. It walks through the array and compares every item with its right neighbor. If the left one is bigger, they swap places. After one pass through the array, the biggest item has bubbled up to the end, like a bubble in a glass of soda.

Then it walks through the array again, but it can stop one item earlier, because the last item is already in place. It keeps going until a pass doesn't swap anything. Here's the code:

function bubbleSort(array) {
    for (let end = array.length - 1; end > 0; end--) {
        let swapped = false;
        for (let i = 0; i < end; i++) {
            if (array[i] > array[i + 1]) {
                swap(array, i, i + 1);
                swapped = true;
            }
        }

        // Nothing moved, so the array is sorted
        if (!swapped) {
            break;
        }
    }
}

end is the index of the last item that isn't in place yet, and every pass moves it one step to the left. swapped keeps track of whether the pass swapped anything. If it didn't, no item is bigger than its right neighbor, so the array is sorted, and break stops the loop early.

To sort an array, pass it to the function. Just like sort(), it changes the array itself, and doesn't return a new one:

let numbers = [5, 2, 9, 1];
bubbleSort(numbers);
// numbers = [1, 2, 5, 9]

In the demo below, watch the biggest number move to the right, one swap at a time. After every pass, one more bar on the right turns green:

Starting order
Sound

With 12 numbers in a random order, bubble sort makes about 60 comparisons and 33 swaps. That's fine for 12 items, but the count grows fast, as you'll see in a moment. Bubble sort does have one strength: on an array that's already sorted, it stops after a single pass. Switch Starting order to Sorted, and it's done after 11 comparisons.

Selection sort: pick the smallest item each time

Selection sort looks through the whole array for the smallest item, and swaps it with the first item. Then it looks for the smallest item in the rest of the array, and puts it in second place. It keeps going until it reaches the end:

function selectionSort(array) {
    for (let i = 0; i < array.length - 1; i++) {
        // Find the smallest item from i to the end
        let smallest = i;
        for (let j = i + 1; j < array.length; j++) {
            if (array[j] < array[smallest]) {
                smallest = j;
            }
        }

        // And move it to place i
        if (smallest != i) {
            swap(array, i, smallest);
        }
    }
}

smallest is the index of the smallest item the inner loop has found so far. Everything before i is already sorted, so the inner loop only looks at the items after it. In the demo, the orange bar is the smallest item found so far:

Sound

Selection sort swaps at most once per pass, so with 12 numbers, it never makes more than 11 swaps. That helps when moving an item takes much more effort than looking at it, like rearranging heavy boxes on a shelf. But the inner loop always looks at the whole rest of the array: 11 comparisons the first time, then 10, and so on. That adds up to 66 comparisons for 12 numbers, even when the array was sorted to begin with.

Insertion sort: insert each item where it belongs

Insertion sort is how most people sort a hand of cards. You pick up the cards one by one, and slide each new card to the left until it's in the right place between the cards you already hold.

In the array, the items on the left are the cards in your hand, and they're always sorted. Each new item moves to the left past every bigger item, and stops at the first item that's smaller or equal:

function insertionSort(array) {
    for (let i = 1; i < array.length; i++) {
        let item = array[i];
        let j = i - 1;

        // Shift every bigger item one place to the right
        while (j >= 0 && array[j] > item) {
            array[j + 1] = array[j];
            j--;
        }

        // And drop the item in the gap
        array[j + 1] = item;
    }
}

item is the new card. The while loop shifts every bigger item one place to the right, which leaves a gap. When the loop stops, the item goes into that gap, at j + 1.

In the demo, the red bar that moves to the left is the new item, and the demo counts every step it takes as a shift. Switch Starting order to Nearly sorted to see what insertion sort is good at:

Starting order
Sound

On a nearly sorted array, most items only move a place or two, so insertion sort is done in no time. On an array that's already sorted, it compares each item once with its left neighbor: 11 comparisons for 12 numbers, and not a single shift. That's why Chrome's sort() uses insertion sort for small chunks of an array, as you'll see further down.

Why the simple sorts get slow

On a random array, bubble sort, selection sort and insertion sort compare each item with a large share of the other items. At most, that's n × (n - 1) / 2 comparisons, where n is the number of items: 45 for 10 items, 4,950 for 100 items and 499,500 for 1,000 items. So ten times as many items means about a hundred times as many comparisons.

Programmers describe this with Big O notation. The three simple sorts are O(n²), which you read as "O of n squared": the work grows with n × n, the number of items multiplied by itself. Big O only cares about how fast the work grows, so it leaves out details like the halving in n × (n - 1) / 2. And unless someone says otherwise, a Big O figure usually describes the worst case.

The faster algorithms in the next sections are O(n log n). Here, log n is roughly how many times you can halve n before you reach 1. For 1,000 items, that's about 10, so they need about 10,000 comparisons instead of half a million.

The chart below shows both. The red line is the number of comparisons bubble sort makes in the worst case, and the blue line is n times log n, about what merge sort from the next section needs. Switch Items to 1,000:

Items

With 10 items, the two lines are close, and the simple sorts are often even faster, because each of their steps is so small. That changes quickly as the array grows. At 1,000 items, the blue line hardly leaves the bottom of the chart.

Merge sort: split the array and merge the halves

Merge sort cuts the array in half, sorts each half, and then merges the two sorted halves into one. To sort each half, it does the same thing again: cut, sort and merge. The halves get smaller and smaller, until each one has a single item, and a single item is always sorted.

Merging is the easy part. Both halves are sorted, so the smallest item is always at the front of one of them. Take the smaller of the two front items, add it to the result, and repeat:

function mergeSort(array) {
    if (array.length <= 1) {
        return array;
    }

    // Sort each half, and merge them
    let middle = Math.floor(array.length / 2);
    let left = mergeSort(array.slice(0, middle));
    let right = mergeSort(array.slice(middle));
    return merge(left, right);
}

function merge(left, right) {
    let result = [];
    let i = 0;
    let j = 0;

    // Take the smaller front item, until one half is empty
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result.push(left[i]);
            i++;
        } else {
            result.push(right[j]);
            j++;
        }
    }

    // Then add whatever is left of the other half
    return result.concat(left.slice(i), right.slice(j));
}

mergeSort() calls itself for each half. A function that calls itself is recursive, and the if at the top makes sure it stops: an array with one item or none comes back as it is.

merge() walks through both halves with i and j. When one half runs out, concat() adds the rest of the other half. One of the two slice() calls returns an empty array by then, so only the leftover items get added.

Unlike the other sorting functions so far, mergeSort() doesn't change the array. It returns a new, sorted array, so you use it like this:

let numbers = [5, 2, 9, 1];
numbers = mergeSort(numbers);

In the demo, the purple area shows the two halves that are being merged. The demo writes every merged item straight back into the array, so each red bar is an item that just landed in its spot in the merged part. It counts each of those as a write:

Sound

Merge sort always takes about n log n steps, whatever the starting order. With 12 random numbers, it makes about 30 comparisons, fewer than n log n (about 43), and half as many as bubble sort. The downside is memory: merging needs a second array as big as the part it merges.

Quicksort: split the array around a pivot

Quicksort also splits the array, but in a different way. It picks one item, the pivot, and moves every smaller item to the left of it, so every bigger item ends up on its right. That's called partitioning. Now the pivot is in its final place, and quicksort does the same for the part on its left and the part on its right:

function quickSort(array, low = 0, high = array.length - 1) {
    if (low >= high) {
        return;
    }
    let pivotIndex = partition(array, low, high);
    quickSort(array, low, pivotIndex - 1);
    quickSort(array, pivotIndex + 1, high);
}

function partition(array, low, high) {
    let pivot = array[high];
    let i = low;

    // Move every item smaller than the pivot to the left
    for (let j = low; j < high; j++) {
        if (array[j] < pivot) {
            swap(array, i, j);
            i++;
        }
    }

    // And put the pivot right after them
    swap(array, i, high);
    return i;
}

low and high are the first and the last index of the part that's being sorted. When you call quickSort(numbers), they get their default values: the whole array.

partition() uses the last item as the pivot. i marks the place for the next small item. Every time j finds an item that's smaller than the pivot, it swaps that item to i, and i moves one place to the right. At the end, every item before i is smaller than the pivot, so the pivot goes to i, and partition() returns i, the pivot's new index.

In the demo, the orange bar is the pivot, and the purple area is the part that's being partitioned. Switch Starting order to Sorted:

Pivot
Starting order
Sound

On a sorted array, the last item is always the biggest. Every partition puts all the other items to the left of the pivot and none to the right, so each round only shrinks the unsorted part by one item. Quicksort then needs 66 comparisons for 12 numbers, just like selection sort. It's O(n²) instead of O(n log n).

The fix is a random pivot. Pick a random item, swap it to the end, and partition as before. Then the bad case is very unlikely, whatever the starting order. Add these lines to the start of partition():

// Pick a random item as the pivot, and move it to the end
let random = low + Math.floor(Math.random() * (high - low + 1));
swap(array, random, high);

This gives you a random index from low up to and including high. The tutorial about random numbers in JavaScript explains how a formula like this works. Switch Pivot to Random item, and a sorted array is no problem anymore.

On a random array, quicksort makes only about 33 comparisons for 12 numbers, and in practice, it's often the fastest of all. It sorts the array in place, and every step is small. Its one weak spot is the bad pivot, and the random pivot takes care of that.

Heap sort: sort with a binary heap

Heap sort uses a binary heap: a tree in which every item is at least as big as the two items below it. So the biggest item is always at the top. The tutorial about pathfinding uses a heap too, for A*, an algorithm that finds the shortest path through a game level. There, the heap keeps the cheapest cell to explore at the top, while heap sort keeps the biggest item there.

The heap lives inside the array. For the item at index i, the two items below it are at i × 2 + 1 and i × 2 + 2. So below index 0 are the items at 1 and 2, and below index 1 are the items at 3 and 4.

The items in the second half of the array have nothing below them. Heap sort works in two steps:

  • Build the heap - Go backward through the first half of the array, and let each item sink until no item below it is bigger.
  • Take the top - Swap the top item, which is the biggest, with the last item of the heap. Now it's in its final place at the end. Let the new top item sink, and repeat with a heap that's one item smaller.

Here's the code:

function heapSort(array) {
    for (let i = Math.floor(array.length / 2) - 1; i >= 0; i--) {
        siftDown(array, i, array.length);
    }

    // Move the biggest item to the end, and repair the heap
    for (let end = array.length - 1; end > 0; end--) {
        swap(array, 0, end);
        siftDown(array, 0, end);
    }
}

function siftDown(array, i, size) {
    while (true) {
        let biggest = i;
        let left = i * 2 + 1;
        let right = left + 1;
        if (left < size && array[left] > array[biggest]) {
            biggest = left;
        }
        if (right < size && array[right] > array[biggest]) {
            biggest = right;
        }
        if (biggest == i) {
            return;
        }
        swap(array, i, biggest);
        i = biggest;
    }
}

siftDown() lets an item sink: it swaps the item with the bigger of the two items below it, until neither of them is bigger. size is how much of the array still belongs to the heap. Everything after it is already sorted.

The demo shows the heap as a tree above the bars. The purple bars are the heap, in the same order as the tree: row by row, from left to right. Watch the biggest number rise to the top, and then move to the end of the array:

Sound

Heap sort is always O(n log n), like merge sort, and it doesn't need a second array. But it jumps all over the array, and a computer is faster at reading items that are close together, so heap sort is a bit slower than quicksort in practice.

Race the sorting algorithms

So which algorithm is the fastest? The race below runs all six on the same array of 40 numbers. Every frame, each algorithm takes the same number of steps, where a step is one comparison or one move: a swap, a shift or a write. Pick a starting order, and click Start the race:

Starting order

The winner depends on the starting order. Here's what usually happens with each one:

  • Random - Quicksort wins, with merge sort and heap sort behind it. Bubble sort needs about four times as many steps as quicksort.
  • Nearly sorted - Insertion sort and bubble sort are done almost right away. Quicksort, which won the race on a random array, is now one of the slowest: with the last item as the pivot, a nearly sorted array is almost its worst case.
  • Reversed - Merge sort and heap sort win. Quicksort ends up in the middle, because a reversed array is just as bad for it as a sorted one. Every pair of items is in the wrong order, so insertion sort and bubble sort make the most moves possible and come last.
  • Many duplicates - The array has only four different numbers. Quicksort and merge sort are in front again, and bubble sort comes last.

No algorithm wins every race. That's why Chrome's sort() combines two of them: merge sort and insertion sort. A stable algorithm keeps equal items in their original order, as the next section explains. Here are all six side by side:

  • Bubble sort - O(n²). Stable. Fast on an array that's already sorted, slow on everything else.
  • Selection sort - O(n²). Not stable. Always the same number of comparisons, but very few swaps.
  • Insertion sort - O(n²). Stable. The best choice for small and nearly sorted arrays.
  • Merge sort - O(n log n). Stable. Fast whatever the order, but needs a second array.
  • Quicksort - O(n log n) on average, O(n²) with bad pivots. Not stable. Usually the fastest in practice.
  • Heap sort - O(n log n). Not stable. Fast whatever the order, without a second array.

Stable and unstable sorting

Sometimes two items are equal. Say you sort the players of a game by score, and two players both have 120 points. A stable sort keeps them in the order they had before: if Ava came before Mia in the array, she still does afterward. An unstable sort might swap them.

That matters when you sort by two things. Sort the players by name first, and then by score with a stable sort, and players with the same score stay in alphabetical order.

The cards below show the numbers 1 to 4, each number once in red and once in blue. The top row shows the cards before sorting, and the bottom row shows them sorted by number. Switch Algorithm to Selection sort, and keep an eye on the colors:

Algorithm

With insertion sort, two cards with the same number stay in the order they had in the top row. Insertion sort only moves an item past bigger items, so equal items never jump over each other. Selection sort swaps the smallest item to the front, and that swap can throw another card far back, past a card with the same number. The demo marks those cards with a red border.

Bubble sort, insertion sort and merge sort are stable. Merge sort owes that to the <= in merge(): when two front items are equal, it takes the one from the left half first. Selection sort, quicksort and heap sort aren't stable.

Sort arrays with JavaScript's sort()

In your own code, use the sort() method that every array has. It's fast, it's well tested and it only takes one line. There's one surprise, though:

let scores = [10, 9, 100, 1];
scores.sort();
// scores = [1, 10, 100, 9]

Without a compare function, sort() turns every item into a string, and compares the strings character by character, like words in a dictionary. "10" starts with a 1, so it comes before "9". To sort numbers, pass a compare function:

scores.sort((a, b) => a - b);
// scores = [1, 9, 10, 100]

sort() calls the compare function with two items, a and b. If it returns a negative number, a goes first. If it returns a positive number, b goes first, and 0 means the two are equal. a - b does exactly that for numbers. For the biggest number first, use b - a.

Objects work the same way. This sorts the players from the highest score down, and players with the same score by name:

let players = [
    {name: 'Mia', score: 120},
    {name: 'Sam', score: 95},
    {name: 'Ava', score: 120}
];

players.sort(function (a, b) {
    if (a.score != b.score) {
        return b.score - a.score;
    }
    return a.name.localeCompare(b.name);
});
// Ava 120, Mia 120, Sam 95

localeCompare() compares two strings the way people expect, so capital letters and accented letters end up in the right place. It returns a negative number, a positive number or 0, just like a compare function should.

sort() changes the array itself. If you still need the original order, use toSorted(), which all modern browsers have supported since 2023. It returns a sorted copy, and leaves the array as it was:

let ranking = scores.toSorted((a, b) => b - a);

So which algorithm does sort() use? The JavaScript standard doesn't say, but since 2019, it does require the sort to be stable. Chrome and Node.js use TimSort, a mix of merge sort and insertion sort. It looks for runs of items that are already in order, sorts short pieces with insertion sort, and merges the pieces like merge sort. That makes it fast on random arrays, and very fast on arrays that are nearly sorted, which happens a lot in real code.

One more thing: don't shuffle an array with sort() and a compare function that returns a random number. The tutorial about random numbers in JavaScript shows why that isn't fair, and how to shuffle an array properly.

Use sorting in a game: draw characters in the right order

In a game seen from above, like a top-down RPG, characters walk in front of trees and behind them. The canvas has no sense of depth, though: whatever you draw last ends up on top. So you have to draw everything in the right order, from back to front.

In a top-down game, back to front simply means from top to bottom on the screen. A character lower on the screen is closer to you, so it's drawn later. Sort your game objects by their y position before you draw them:

function draw() {
    // Whoever stands lower on the screen is in front, so draw them last
    gameObjects.sort((a, b) => a.y - b.y);

    for (let i = 0; i < gameObjects.length; i++) {
        gameObjects[i].draw();
    }
}

Here, y is the bottom of each object, where it touches the ground, and not the top of its image. If y in your own code is the top of the image, compare the bottoms instead: (a.y + a.height) - (b.y + b.height).

Move your mouse over the garden below, or touch it, to walk the red character around the trees. Then switch Draw order to Sorted by y position:

Draw order

With Unsorted, the demo draws the trees first and the characters after them, so the characters always walk over the trees, even when they're behind one. With Sorted by y position, every tree and character is drawn in the right order.

Sorting every frame sounds like a lot of work. But between two frames, the characters only move a tiny bit, so the array is nearly sorted. That's exactly where TimSort and insertion sort are at their fastest.

Sorting also comes in handy for a high score list. The tutorial about game states keeps a single high score. For a top 5, add the new score to a list, sort the list and keep the first five:

let highScores = [];

function addHighScore(name, score) {
    highScores.push({name: name, score: score});
    highScores.sort((a, b) => b.score - a.score);

    // Keep the five best scores
    highScores = highScores.slice(0, 5);
}

To keep the list when the player closes the page, save it with local storage. And the pathfinding tutorial first uses sort() on the list of cells that A* still has to explore, and later replaces that list with a binary heap, the same structure that heap sort uses.

Build your own sorting visualizer with sound

Building a visualizer like the demos on this page is a popular project. The tricky part is that a sorting function runs from start to finish in one go, so the canvas only gets to show the result. You want the function to stop after every step, so you can draw the bars in between.

A generator function does exactly that. Add a * after function, and put yield wherever the function should pause. Here's bubble sort as a generator, which yields the indexes of the two items it compares:

function* bubbleSort(array) {
    for (let end = array.length - 1; end > 0; end--) {
        let swapped = false;
        for (let i = 0; i < end; i++) {
            yield [i, i + 1];
            if (array[i] > array[i + 1]) {
                swap(array, i, i + 1);
                swapped = true;
            }
        }
        if (!swapped) {
            break;
        }
    }
}

Calling the function doesn't run it yet. It gives you a generator object, and every call to its next() method runs the function until the next yield:

let values = [5, 2, 9, 1];
let steps = bubbleSort(values);

steps.next();
// {value: [0, 1], done: false}

When the function reaches its end, next() returns done: true, and the array is sorted.

Merge sort and quicksort call themselves. In a generator, a plain call would only create a new generator, without running it. yield* runs the inner generator and passes every step it yields on through the outer one. You need it whenever one generator calls another, like siftDown() in heap sort.

In this version of quicksort, the partitioning is inside the function, so its steps are part of the same generator:

function* quickSort(array, low = 0, high = array.length - 1) {
    if (low >= high) {
        return;
    }

    // Move everything smaller than the pivot to the left
    let pivot = array[high];
    let i = low;
    for (let j = low; j < high; j++) {
        yield [j, high];
        if (array[j] < pivot) {
            swap(array, i, j);
            i++;
        }
    }
    swap(array, i, high);

    yield* quickSort(array, low, i - 1);
    yield* quickSort(array, i + 1, high);
}

Merge sort needs one more change. The version earlier on this page builds new arrays, but a visualizer draws a single array. So the example code at the end of this page merges the halves back into the array itself.

It copies the two halves with slice() first, so it doesn't overwrite items it still needs. Then it writes the smaller of the two front items back into the array, one place at a time.

Once the right half runs out, it takes the rest from the left half. If the left half runs out first, the rest of the right half is already in place. Each write yields the same index twice, because there's only one bar to color.

Then a game loop takes a few steps every frame and draws the bars. steps holds the generator, and current holds the two indexes from the last step. values holds the numbers 1 to barCount, which is 50 in the example code, so values[i] / barCount is a fraction between 0 and 1:

function gameLoop(timeStamp) {
    let secondsPassed = (timeStamp - oldTimeStamp) / 1000;
    oldTimeStamp = timeStamp;
    secondsPassed = Math.min(secondsPassed, 0.1);

    // Take a few steps of the sorting algorithm every frame
    stepTimer += secondsPassed * stepsPerSecond;
    while (steps && stepTimer >= 1) {
        stepTimer--;
        let next = steps.next();
        if (next.done) {
            steps = null;
            current = null;
        } else {
            current = next.value;
        }
    }
    stepTimer = Math.min(stepTimer, 1);

    if (current) {
        playTone(values[current[0]]);
    }
    draw();
    window.requestAnimationFrame(gameLoop);
}

function draw() {
    context.clearRect(0, 0, canvas.width, canvas.height);
    let barWidth = canvas.width / values.length;
    for (let i = 0; i < values.length; i++) {
        let barHeight = values[i] / barCount * canvas.height;
        let isActive =
            current && (i == current[0] || i == current[1]);
        context.fillStyle = isActive ? '#ff8080' : '#0099b0';
        context.fillRect(
            i * barWidth, canvas.height - barHeight,
            barWidth - 1, barHeight
        );
    }
}

stepsPerSecond sets the speed, and secondsPassed keeps it the same on every screen, as the tutorial about the JavaScript game loop explains. stepTimer adds up the steps that are due, and the while loop takes them. Math.min() caps secondsPassed, so the sort doesn't jump ahead when you come back from another tab. It also caps stepTimer, so steps don't pile up while nothing is being sorted.

draw() uses fillRect() to draw each bar with a height that matches its value, and colors the two bars from the last step red. The tutorial about drawing on the canvas explains fillRect().

For the sound, play a short note every frame with an OscillatorNode from the Web Audio API. The tutorial about game audio explains the AudioContext, and why the browser only plays sound after a click. In the example code, toggleSound() creates the audioContext the first time you click the sound button, and switches soundOn between true and false. Turn the value of the bar into a frequency, so a taller bar plays a higher note:

function playTone(value) {
    if (!soundOn) {
        return;
    }
    let now = audioContext.currentTime;
    let oscillator = audioContext.createOscillator();
    oscillator.type = 'triangle';

    // A taller bar plays a higher note, from 200 to 1000 Hz
    oscillator.frequency.value = 200 + value / barCount * 800;

    // A short beep that fades out quickly
    let gain = audioContext.createGain();
    gain.gain.setValueAtTime(0.1, now);
    gain.gain.exponentialRampToValueAtTime(0.001, now + 0.1);

    oscillator.connect(gain);
    gain.connect(audioContext.destination);
    oscillator.start(now);
    oscillator.stop(now + 0.1);
}

The GainNode fades the note out in a tenth of a second, so it doesn't click when it stops. An exponential ramp can't reach 0, so it goes down to 0.001, which you can't hear anymore. At 60 frames per second, the notes blur together into the sound you hear in the demos.

Common questions about sorting algorithms

Which sorting algorithm is the fastest?

None of them is the fastest every time. For a big random array, quicksort is usually the fastest in practice, with merge sort and heap sort close behind. For a small or nearly sorted array, insertion sort beats them all. The sort() in Chrome combines merge sort and insertion sort, so it's fast in both cases.

What sorting algorithm does JavaScript's sort() use?

The JavaScript standard doesn't say which algorithm to use, only that the sort has to be stable. V8, the engine in Chrome and Node.js, uses TimSort, a mix of merge sort and insertion sort. Until 2018, V8 used quicksort, with insertion sort for short arrays.

Why does sort() put 10 before 9?

Without a compare function, sort() compares the items as strings. "10" starts with "1", which comes before "9". To sort numbers, pass a compare function: numbers.sort((a, b) => a - b).

Is JavaScript's sort() stable?

Yes. Since ES2019, the standard requires it, and all major browsers have a stable sort. Items that are equal keep the order they had before.

Which sorting algorithm should I use for an array that's nearly sorted?

Insertion sort. Each item only moves a few places, so it takes about n steps instead of n². In JavaScript, you can just use sort(): TimSort finds the parts that are already in order, and is very fast on them.

Can you sort faster than O(n log n)?

Not by comparing items: O(n log n) is the limit for any algorithm that compares two items at a time. But if the items are whole numbers in a small range, like scores from 0 to 100, counting sort is faster. It counts how often each number appears, and then writes the numbers out in order. That takes O(n + k) steps, where k is the size of the range.

What's the difference between merge sort and quicksort?

Both split the array and sort the parts. Merge sort splits in the middle and does the work when it merges, so it's always O(n log n) and stable, but it needs a second array. Quicksort does the work when it partitions around a pivot. It sorts in place and is usually faster, but it isn't stable, and a bad pivot can make it slow.

Do I need to know sorting algorithms for coding interviews?

Often, yes. Interviewers rarely ask you to write bubble sort, but they do expect you to know the Big O of the common sorts, explain merge sort or quicksort, and pick the right approach for a problem. In real code, you'd use the built-in sort().

Example code: a sorting visualizer with sound

Here's an example page that puts the basics from this tutorial together in a single HTML file: the six algorithms as generators, a canvas with 50 bars, and a button for each algorithm. Click the Sound: off button to turn on the sound. Paste the code below into an HTML file and open it in your browser:

Conclusion

Every sorting algorithm does the same two things: it compares two items, and it moves them. Bubble sort, selection sort and insertion sort do that in the simplest way, but they slow down quickly on big arrays. Merge sort, quicksort and heap sort are smarter about it and stay fast as arrays grow. And in your own code, sort() with a compare function does it all for you, stable and fast.

Want to see a heap do more than sort? The tutorial about pathfinding uses one to find the shortest path through a maze.

That's all for now. If you have any questions, feel free to ask them in the comment section. You can