Sorting Algorithms

Algorithms to arrange elements in order. Key ones: Bubble O(n^2), Merge O(n log n), Quick O(n log n) avg, Heap O(n log n).

Syntax

dsa

// Merge sort divide-and-conquer:
split -> sort halves -> merge

Example

dsa

// Merge Sort - O(n log n) always:
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

// Quick Sort - O(n log n) average, O(n^2) worst