Skip to content
Tutorials Center
My learning

Topics

Lesson 143 of 156 · Data Structures and Algorithms

Searching and Sorting Algorithms

Write linear and binary search, bubble, selection, insertion, merge and quick sort in JavaScript, understand Big-O notation, and watch a sort run step by step.

An algorithm is a precise recipe for solving a problem: a list of steps that always ends with an answer. Searching ("is this value here, and where?") and sorting ("put these in order") are the two most common problems in programming, and the classic solutions to them teach you how to think about speed.

You will rarely write your own sort in real code, because array.sort() is fast and well tested (see Sorting Arrays). But knowing how sorting and searching work helps you pick the right built-in, spot slow code before it ships, and answer the questions that come up in almost every technical interview. In this lesson you will learn Big-O notation, two searches, four sorts, and you will watch a sort happen one step at a time.

Big-O: how work grows

Timing code in milliseconds is useful, but the result depends on your computer, your browser and the data. Big-O notation describes something more stable: how the amount of work grows as the input gets bigger. If you double the number of items, does the work stay the same, double, or quadruple?

Big-O Name Example 1,000 items → about
O(1) Constant arr[5], map.get(key) 1 step
O(log n) Logarithmic Binary search 10 steps
O(n) Linear arr.includes(x), one loop 1,000 steps
O(n log n) Linearithmic Merge sort, arr.sort() 10,000 steps
O(n²) Quadratic A loop inside a loop, bubble sort 1,000,000 steps

Big-O ignores constants and small terms: a loop that runs 2n + 3 times is still O(n), because for large inputs the shape of the growth is what matters. It also usually describes the worst case unless you say otherwise.

The quickest way to feel the difference is to count operations:

JS Counting steps as n grows

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Going from 1,000 to 2,000 items adds one step to the logarithmic loop, doubles the linear one and quadruples the quadratic one. That is why an O(n²) algorithm that feels instant in testing can freeze a page with real data.

The simplest search checks every item from the start until it finds a match. It works on any array, sorted or not, and takes O(n) time in the worst case (the value is last, or missing).

JavaScript
function linearSearch(items, target) {
  for (let i = 0; i < items.length; i++) {
    if (items[i] === target) return i;
  }
  return -1;
}

This is what indexOf(), includes() and find() do internally (see Searching Arrays). For a few hundred items, or a search you run only once, linear search is the right choice. It is simple and needs no preparation.

If the array is sorted, you can do far better. Look at the middle item. If it's the target, you are done. If the target is smaller, it can only be in the left half; if bigger, only in the right half. Throw away the other half and repeat. Each step halves the remaining range, so a million sorted items take at most about 20 comparisons: O(log n).

JS Binary search, step by step

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Binary search is famous for off-by-one bugs. Three details keep it correct:

  • The loop runs while low <= high (with <, a one-item range would be skipped).
  • After a comparison, move past the middle: mid + 1 or mid - 1. Setting low = mid can loop forever.
  • (low + high) >>> 1 is a common way to halve a sum and round down. Plain Math.floor((low + high) / 2) is equally safe in JavaScript, because numbers don't overflow at 32 bits here.

Binary search on unsorted data gives wrong answers, not errors. It will happily return -1 for a value that is in the array. Sort first, or keep your data sorted as you insert. Sorting costs O(n log n), so it only pays off if you search the same array many times.

Bubble sort

Now to sorting. Bubble sort walks through the array comparing neighbors and swapping any pair that is in the wrong order. After the first pass, the largest value has "bubbled" to the end. After the second pass, the second largest is in place, and so on.

JavaScript
function bubbleSort(input) {
  const a = [...input];
  for (let end = a.length - 1; end > 0; end--) {
    let swapped = false;
    for (let i = 0; i < end; i++) {
      if (a[i] > a[i + 1]) {
        [a[i], a[i + 1]] = [a[i + 1], a[i]];
        swapped = true;
      }
    }
    if (!swapped) break; // already sorted: stop early
  }
  return a;
}

It is easy to understand and terribly slow: O(n²) comparisons in the worst case. Its only real use is teaching. The swapped flag at least makes it stop early when the data is already sorted.

Insertion sort

Insertion sort works the way many people sort a hand of cards. Take the next item, slide it left past every larger item, and drop it into place. The left part of the array is always sorted and grows by one item each round.

JavaScript
function insertionSort(input) {
  const a = [...input];
  for (let i = 1; i < a.length; i++) {
    const current = a[i];
    let j = i - 1;
    while (j >= 0 && a[j] > current) {
      a[j + 1] = a[j]; // shift the bigger item right
      j--;
    }
    a[j + 1] = current;
  }
  return a;
}

Insertion sort is also O(n²) in the worst case, but it is very fast on small or nearly sorted arrays: if every item is already close to its place, the inner loop barely runs. That is why real sort implementations, including the one inside V8 (Chrome, Edge and Node.js), switch to insertion sort for short runs.

Watch it work

The editor below sorts a row of bars with insertion sort. The sort is written as a generator that pauses (yield) after every comparison, so you can step through it, or press Play:

Insertion sort visualizer

Orange bars are being compared, green bars are in the sorted part, and gray bars are still waiting. Try changing insertionSortSteps into a bubble sort and compare how the bars move.

Selection sort

Selection sort takes a different approach from the two sorts above: it keeps asking, "which of the remaining items belongs next?" On each round it scans the unsorted part of the array to find the smallest item, then swaps it into the first unsorted position. After round one the smallest value is in place; after round two the second smallest, and so on.

JavaScript
function selectionSort(input) {
  const a = [...input];
  for (let i = 0; i < a.length - 1; i++) {
    let min = i;                                   // index of the smallest seen so far
    for (let j = i + 1; j < a.length; j++) {
      if (a[j] < a[min]) min = j;
    }
    if (min !== i) [a[i], a[min]] = [a[min], a[i]];
  }
  return a;
}

Selection sort always makes about n²/2 comparisons, even when the array is already sorted, so it is O(n²) in the best, average and worst case. Its one selling point is that it does very few writes: at most n - 1 swaps. That can matter when writing is expensive (flash memory, for example) but comparing is cheap. In ordinary JavaScript code it has no practical use over sort().

JS Selection sort: comparisons, swaps and stability

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The first run shows 10 comparisons for five items whether the input is reversed or already sorted; only the swap count changes (2 and 0). The last line shows that selection sort is not stable: item a started before b (both of size 2), but swapping a with the smaller c carried it behind b. See Sorting Arrays for why stability matters when you sort records by one field after another.

Merge sort

Merge sort uses a strategy called divide and conquer. Split the array in half, sort each half (by calling merge sort again, using recursion), then merge the two sorted halves into one. Merging is easy: repeatedly take the smaller of the two front items.

The array can only be halved about log n times, and each level of halving does O(n) merging work, so merge sort is O(n log n) in every case, best and worst. It is also stable: equal items keep their original order. The cost is extra memory for the merged arrays.

JS Merge sort

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Quick sort

Quick sort also divides and conquers, but in a different way. Pick one item as the pivot. Put everything smaller than the pivot on its left and everything bigger on its right; the pivot is now in its final place. Then quick sort the left and right parts.

JavaScript
function quickSort(items) {
  if (items.length <= 1) return items;

  const pivot = items[Math.floor(Math.random() * items.length)];
  const smaller = items.filter((x) => x < pivot);
  const equal = items.filter((x) => x === pivot);
  const larger = items.filter((x) => x > pivot);

  return [...quickSort(smaller), ...equal, ...quickSort(larger)];
}

This version is short and readable, but it creates many new arrays. Production versions partition in place by swapping items inside one array, which makes quick sort very fast in practice and light on memory.

Quick sort averages O(n log n), but its worst case is O(n²): if the pivot is always the smallest or largest item, each step only removes one item. Choosing the first item as pivot triggers this on already sorted input, which is common in real data. A random pivot (as above) or the "median of three" trick makes the worst case extremely unlikely. Quick sort is also not stable.

Comparing the sorts

Algorithm Best Average Worst Extra memory Stable
Bubble sort O(n) O(n²) O(n²) O(1) Yes
Selection sort O(n²) O(n²) O(n²) O(1) No
Insertion sort O(n) O(n²) O(n²) O(1) Yes
Merge sort O(n log n) O(n log n) O(n log n) O(n) Yes
Quick sort O(n log n) O(n log n) O(n²) O(log n) in place No
array.sort() in modern engines O(n) O(n log n) O(n log n) O(n) Yes

The theory shows up clearly in practice. Run this race on 5,000 random numbers:

JS Sorting race

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Bubble sort is usually tens or hundreds of times slower, and the gap widens fast as you increase the length. The built-in sort typically wins: V8 and the other major engines use TimSort or a similar hybrid that merges naturally sorted runs and uses insertion sort for short pieces. It is stable and O(n log n), so in real code, always reach for sort() or toSorted() with a comparator.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. An algorithm takes 1 second for 1,000 items. Roughly how long should it take for 2,000 items if it is O(n²)?

    Doubling n squares into four times the work: (2n)² = 4n². An O(n) algorithm would take about 2 seconds, and O(log n) barely any longer.
  2. 2. What must be true before you can use binary search on an array?

    Binary search decides which half to discard by comparing with the middle item, which only works if the items are in order. It works with strings and duplicates too, given a consistent order.
  3. 3. Why is insertion sort used inside real-world hybrid sorts?

    When items are already close to their places, the inner loop barely runs, so insertion sort beats more complex sorts on short runs.
  4. 4. What causes quick sort's O(n²) worst case?

    Bad pivots make lopsided splits. A random pivot or median-of-three makes that extremely unlikely.
  5. 5. Which sort guarantees O(n log n) in every case and is stable, at the cost of extra memory?

    Merge sort always splits evenly and merges with <=, keeping equal items in order. It needs O(n) extra space for the merged arrays.

Summary

  • Big-O describes how work grows with input size: O(1), O(log n), O(n), O(n log n), O(n²). Constants are ignored.
  • Linear search checks every item, O(n), and works on any array. Binary search halves a sorted range each step, O(log n).
  • Bubble and insertion sort are simple O(n²) sorts; insertion sort shines on small or nearly sorted data. Selection sort is also O(n²) but makes at most n - 1 swaps (and is not stable).
  • Merge sort splits, sorts and merges: always O(n log n) and stable, with extra memory.
  • Quick sort partitions around a pivot: O(n log n) on average, O(n²) with bad pivots, and not stable.
  • In real code, use the built-in sort() or toSorted(): it is a stable, O(n log n) hybrid.

Next: Heaps, Priority Queues and Deques.