Sorting Algorithms – Full-Stack

Sorting Algorithms

Master efficient data organization techniques – from basic quadratic sorts to advanced divide-and-conquer algorithms.

1. Bubble Sort, Selection Sort, Insertion Sort

Simple Comparison-Based Sorts

These algorithms are the fundamental building blocks of sorting techniques. They work by repeatedly comparing adjacent elements and swapping them if they’re in the wrong order.

Easy to Understand

With straightforward implementations, these algorithms are perfect for beginners learning sorting concepts and understanding algorithmic thinking.

Bubble Sort Implementation
function bubbleSort(arr) {
    let n = arr.length;
    for (let i = 0; i < n-1; i++) {
        for (let j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // Swap elements
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
            }
        }
    }
    return arr;
}

Suitable for Small Datasets

  • Excellent for nearly sorted data
  • Minimal code complexity
  • Low memory overhead
  • Adaptive (Insertion Sort performs well on small arrays)

Mostly O(n²) Complexity

Algorithm Best Case Average Case Worst Case Space
Bubble Sort O(n) O(n²) O(n²) O(1)
Selection Sort O(n²) O(n²) O(n²) O(1)
Insertion Sort O(n) O(n²) O(n²) O(1)

2. Merge Sort

Divide and Conquer Approach

Merge sort recursively divides the array into halves until each subarray contains a single element, then merges them back in sorted order.

Splits Array into Halves

Merge Sort Process

[8, 3, 5, 1, 7, 2, 6, 4]

[8, 3, 5, 1] | [7, 2, 6, 4]

[8, 3] [5, 1] | [7, 2] [6, 4]

[3, 8] [1, 5] | [2, 7] [4, 6]

[1, 3, 5, 8] | [2, 4, 6, 7]

[1, 2, 3, 4, 5, 6, 7, 8]

Stable Sort

Merge sort preserves the relative order of equal elements, making it suitable for sorting objects with multiple keys.

Merge Sort Implementation
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);
}

function merge(left, right) {
    let result = [];
    let i = 0, j = 0;
    
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result.push(left[i]);
            i++;
        } else {
            result.push(right[j]);
            j++;
        }
    }
    
    return result.concat(left.slice(i)).concat(right.slice(j));
}

O(n log n) Complexity

O(n log n)
All Cases
O(n)
Space Complexity
Stable
Preserves Order

3. Quick Sort

Divide and Conquer

Quick sort selects a 'pivot' element and partitions the array around the pivot, placing smaller elements to the left and larger elements to the right.

Uses Pivot Element

The choice of pivot significantly affects performance. Common strategies include selecting the first, last, middle, or random element.

Faster in Average Cases

  • Average Case: O(n log n)
  • Worst Case: O(n²) (rare with good pivot selection)
  • Space Complexity: O(log n)
  • Not stable
Quick Sort Implementation
function quickSort(arr, low = 0, high = arr.length - 1) {
    if (low < high) {
        const pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
    return arr;
}

function partition(arr, low, high) {
    const pivot = arr[high];
    let i = low - 1;
    
    for (let j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
    }
    
    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
    return i + 1;
}

In-Place Sorting

Quick sort sorts the array within itself without requiring significant additional storage, making it memory efficient.

4. Heap Sort

Uses Binary Heap

Heap sort uses a binary heap data structure to sort elements. It first builds a max-heap from the input data, then repeatedly extracts the maximum element.

Selection-Style Removal

After building the heap, the algorithm repeatedly removes the largest element and rebuilds the heap until all elements are sorted.

O(n log n) Complexity

O(n log n)
All Cases
O(1)
Space Complexity
Not Stable
Doesn't Preserve Order
Heap Sort Implementation
function heapSort(arr) {
    let n = arr.length;
    
    // Build max heap
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    
    // Extract elements from heap
    for (let i = n - 1; i > 0; i--) {
        [arr[0], arr[i]] = [arr[i], arr[0]];
        heapify(arr, i, 0);
    }
    return arr;
}

function heapify(arr, n, i) {
    let largest = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    
    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;
    
    if (largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        heapify(arr, n, largest);
    }
}

Good for Priority-Based Problems

Heap sort is particularly useful for priority queue implementations and problems requiring frequent access to the largest or smallest element.

Project: Sorting Algorithm Visualizer

Build an interactive tool to visualize how different sorting algorithms work step by step.

Project Starter Code
class SortingVisualizer {
    constructor() {
        this.array = [];
        this.algorithm = 'bubble';
        this.speed = 100;
    }
    
    generateArray(size = 50) {
        this.array = Array.from({length: size}, () => 
            Math.floor(Math.random() * 100) + 1
        );
    }
    
    async visualizeSort(algorithm) {
        switch(algorithm) {
            case 'bubble':
                await this.bubbleSort();
                break;
            case 'merge':
                await this.mergeSort();
                break;
            case 'quick':
                await this.quickSort();
                break;
            case 'heap':
                await this.heapSort();
                break;
        }
    }
    
    // Add sorting method implementations here
}