Welcome to the Algorithm Series: Sorting Algorithms

This article is part of the Discovering JavaScript’s Hidden Secrets series. After covering searching algorithms, we now shift our focus to sorting algorithms — a cornerstone of efficient data manipulation and performance optimization in computer science.

\n\n

What Are Sorting Algorithms?

A sorting algorithm is a step-by-step procedure used to reorder elements in a collection (like an array or list), usually in ascending or descending order. Sorting is essential in computing because it improves the efficiency of search operations, enhances data presentation, and underpins key operations in databases, machine learning pipelines, and UI design.

\n\n

Why Are Sorting Algorithms Important?

Sorting algorithms are foundational for:

Fast Data Retrieval: Algorithms like Binary Search require sorted data to operate efficiently (O(log n)). Database indexing, autocomplete systems, and filtering rely on sorted structures.

Efficient Processing: Sorting assists in grouping, aggregating, and comparing data. For example, sorting enables streamlined JOIN and ORDER BY operations in SQL.

Enhanced User Experience: Product listings (e.g., by price or rating), recommendation feeds (Netflix, Spotify), and dashboards often rely on sorting to improve usability.

Memory Optimization: Sorted data enables techniques like run-length encoding and improves caching behavior in large systems.

\n\n

Common Types of Sorting Algorithms

Here are widely-used sorting algorithms, each with its own trade-offs in time complexity, memory use, and implementation style:

Bubble Sort

Insertion Sort

QuickSort

Merge Sort

Heap Sort

Radix Sort

\n\n

Bubble Sort

A simple, intuitive algorithm that repeatedly compares and swaps adjacent elements if they’re in the wrong order. Best used for small or nearly sorted datasets.

Time Complexity: O(n²)

Design Pattern: Brute Force

Use Case: Small datasets, teaching concept

function bubbleSort(arr) {\n  let n = arr.length;\n  for (let i = 0; i < n - 1; i++) {\n    let swapped = false;\n    for (let j = 0; j < n - i - 1; j++) {\n      if (arr[j] > arr[j + 1]) {\n        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];\n        swapped = true;\n      }\n    }\n    if (!swapped) break;\n  }\n  return arr;\n}\n

\n\n

Insertion Sort

Builds the final sorted array one element at a time. Effective on small or nearly sorted datasets.

Time Complexity: O(n²)

Design Pattern: Brute Force

Use Case: Nearly sorted arrays, small input size

function insertionSort(arr) {\n  for (let i = 1; i < arr.length; i++) {\n    let current = arr[i];\n    let j = i - 1;\n    while (j >= 0 && arr[j] > current) {\n      arr[j + 1] = arr[j];\n      j--;\n    }\n    arr[j + 1] = current;\n  }\n  return arr;\n}\n

\n\n

QuickSort

A fast, recursive algorithm that uses the divide-and-conquer approach by selecting a pivot and partitioning the array around it.

Time Complexity: Best/Average: O(n log n), Worst: O(n²)

Design Pattern: Divide and Conquer

Use Case: General-purpose, large datasets

function quickSort(arr, low = 0, high = arr.length - 1) {\n  if (low < high) {\n    const pivotIndex = partition(arr, low, high);\n    quickSort(arr, low, pivotIndex - 1);\n    quickSort(arr, pivotIndex + 1, high);\n  }\n  return arr;\n}\n\nfunction partition(arr, low, high) {\n  const pivot = arr[high];\n  let i = low;\n  for (let j = low; j < high; j++) {\n    if (arr[j] <= pivot) {\n      [arr[i], arr[j]] = [arr[j], arr[i]];\n      i++;\n    }\n  }\n  [arr[i], arr[high]] = [arr[high], arr[i]];\n  return i;\n}\n

\n\n

Merge Sort

Another divide-and-conquer algorithm that splits the array into halves, recursively sorts them, and merges the sorted halves.

Time Complexity: O(n log n)

Design Pattern: Divide and Conquer

Use Case: Stable sort, large data with guaranteed performance

function mergeSort(arr) {\n  if (arr.length <= 1) return arr;\n  const mid = Math.floor(arr.length / 2);\n  const left = mergeSort(arr.slice(0, mid));\n  const right = mergeSort(arr.slice(mid));\n  return merge(left, right);\n}\n\nfunction merge(left, right) {\n  const result = [];\n  let i = 0, j = 0;\n  while (i < left.length && j < right.length) {\n    result.push(left[i] < right[j] ? left[i++] : right[j++]);\n  }\n  return result.concat(left.slice(i)).concat(right.slice(j));\n}\n

\n\n

Heap Sort

Uses a binary heap to sort elements by first building a max-heap and then extracting the maximum repeatedly.

Time Complexity: O(n log n)

Design Pattern: Heap-based / Divide and Conquer

Use Case: In-place sort with good worst-case performance

function heapSort(arr) {\n  const n = arr.length;\n  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {\n    heapify(arr, n, i);\n  }\n  for (let i = n - 1; i >

Sources:

Explore More...