Sorting and recursion

Sorting

Bubble sort — O(n²)

The simplest to understand: it compares adjacent pairs and swaps them if they are in the wrong order, repeating until there are no changes.

function bubbleSort(arr) {
  const a = [...arr];
  for (let i = 0; i < a.length; i++) {
    for (let j = 0; j < a.length - 1 - i; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
      }
    }
  }
  return a;
}

Merge sort and quick sort — O(n log n)

For large data, divide-and-conquer algorithms are used:

• Merge sort: splits the array in half, sorts each half, and merges them in order.
• Quick sort: picks a pivot, places the smaller ones on one side and the larger ones on the other, and repeats on each side.

Both are much faster than bubble sort for large inputs. In practice, Array.prototype.sort() already uses an efficient algorithm.

Recursion

A recursive function calls itself with a smaller problem until it reaches a base case.

function factorial(n) {
  if (n <= 1) return 1;       // base case
  return n * factorial(n - 1); // recursive case
}

function fibonacci(n) {
  if (n < 2) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

The naive recursive Fibonacci is O(2ⁿ): it recomputes the same values over and over. It can be optimized with memoization or with a loop.

Examples

Bubble sort with trace

function bubbleSort(arr) {
  const a = [...arr];
  for (let i = 0; i < a.length; i++) {
    for (let j = 0; j < a.length - 1 - i; j++) {
      if (a[j] > a[j + 1]) [a[j], a[j + 1]] = [a[j + 1], a[j]];
    }
  }
  return a;
}
console.log(bubbleSort([5, 2, 8, 1, 9, 3]));

Recursive factorial

function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}
console.log("5! =", factorial(5));