Sorting Algorithms

Bubble Sort

Bubble Sort

Selection Sort

Selection Sort

Merge Sort

Merge Sort

Quick Sort

Quick Sort

Insertion Sort

Insertion Sort

Select a Sorting Algorithm to Visualize & Analyze

Bubble Sort

Worst Case: O(n²)
Best Case: O(n)
Space Complexity: O(1)
Stable: Yes
0
Steps
0
Comparisons
0
Swaps
0ms
Time
Normal
Comparing
Swapping
Sorted

Algorithm Code

function bubbleSort(arr) {
  let n = arr.length;
  let swapped;
  
  for (let i = 0; i < n - 1; i++) {
    swapped = false;
    
    for (let j = 0; j < n - i - 1; j++) {
      // Compare adjacent elements
      if (arr[j] > arr[j + 1]) {
        // Swap if they are in wrong order
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    
    // If no swaps occurred, array is sorted
    if (!swapped) break;
  }
  
  return arr;
}

How Bubble Sort Works

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order.

  • Pass through array: Compare each pair of adjacent elements
  • Swap if needed: If the first element is greater than the second, swap them
  • Repeat: Continue passes until no swaps are needed
  • Optimization: After each pass, the largest element bubbles to the end

Key Characteristics:

  • In-place algorithm (uses only a constant amount of extra memory)
  • Stable (preserves order of equal elements)
  • Time complexity: O(n²) in worst and average cases, O(n) in best case (already sorted)

Selection Sort

Worst Case: O(n²)
Best Case: O(n²)
Space Complexity: O(1)
Stable: No
0
Steps
0
Comparisons
0
Swaps
0ms
Time
Normal
Comparing
Swapping
Sorted
Current Min

Algorithm Code

function selectionSort(arr) {
  let n = arr.length;
  
  for (let i = 0; i < n - 1; i++) {
    // Find the minimum element in unsorted array
    let minIdx = i;
    
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIdx]) {
        minIdx = j;
      }
    }
    
    // Swap the found minimum with the first element
    if (minIdx !== i) {
      [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
    }
  }
  
  return arr;
}

How Selection Sort Works

Selection Sort divides the input list into two parts: a sorted sublist and an unsorted sublist. The algorithm repeatedly finds the minimum element from the unsorted part and moves it to the end of the sorted part.

  • Find minimum: Scan unsorted portion to find smallest element
  • Swap: Swap it with the first unsorted element
  • Expand sorted portion: Move boundary between sorted and unsorted one element to the right
  • Repeat: Continue until entire array is sorted

Key Characteristics:

  • In-place algorithm (uses only a constant amount of extra memory)
  • Not stable (may change order of equal elements)
  • Time complexity: Always O(n²) regardless of input order
  • Makes O(n) swaps (minimum possible)

Merge Sort

Worst Case: O(n log n)
Best Case: O(n log n)
Space Complexity: O(n)
Stable: Yes
0
Steps
0
Comparisons
0
Merges
0ms
Time
Normal
Comparing
Sorted
Left Half
Right Half

Algorithm Code

function mergeSort(arr, left = 0, right = arr.length - 1) {
  if (left >= right) return;
  
  const mid = Math.floor((left + right) / 2);
  
  // Recursively sort both halves
  mergeSort(arr, left, mid);
  mergeSort(arr, mid + 1, right);
  
  // Merge the sorted halves
  merge(arr, left, mid, right);
}

function merge(arr, left, mid, right) {
  const leftArr = arr.slice(left, mid + 1);
  const rightArr = arr.slice(mid + 1, right + 1);
  
  let i = 0, j = 0, k = left;
  
  while (i < leftArr.length && j < rightArr.length) {
    if (leftArr[i] <= rightArr[j]) {
      arr[k] = leftArr[i];
      i++;
    } else {
      arr[k] = rightArr[j];
      j++;
    }
    k++;
  }
  
  // Copy remaining elements
  while (i < leftArr.length) {
    arr[k] = leftArr[i];
    i++;
    k++;
  }
  
  while (j < rightArr.length) {
    arr[k] = rightArr[j];
    j++;
    k++;
  }
}

How Merge Sort Works

Merge Sort is a divide-and-conquer algorithm that divides the input array into two halves, recursively sorts each half, and then merges the sorted halves.

  • Divide: Split the array into two halves
  • Conquer: Recursively sort each half
  • Combine: Merge the two sorted halves
  • Base case: Array of size 1 is already sorted

Key Characteristics:

  • Not in-place (requires O(n) additional memory)
  • Stable (preserves order of equal elements)
  • Time complexity: Always O(n log n) regardless of input
  • Well-suited for large datasets and external sorting

Quick Sort

Worst Case: O(n²)
Best Case: O(n log n)
Space Complexity: O(log n)
Stable: No
0
Steps
0
Comparisons
0
Swaps
0ms
Time
Normal
Comparing
Swapping
Pivot
Left Partition
Right Partition

Algorithm Code

function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    // Partition the array and get pivot index
    const pi = partition(arr, low, high);
    
    // Recursively sort elements before and after partition
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
}

function partition(arr, low, high) {
  // Choose rightmost element as pivot
  const pivot = arr[high];
  
  // Index of smaller element
  let i = low - 1;
  
  for (let j = low; j < high; j++) {
    // If current element is smaller than pivot
    if (arr[j] < pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  
  // Swap pivot to correct position
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  
  return i + 1;
}

How Quick Sort Works

Quick Sort is a divide-and-conquer algorithm that selects a 'pivot' element and partitions the array around the pivot, placing smaller elements to the left and larger elements to the right.

  • Choose pivot: Select an element as pivot (here: last element)
  • Partition: Rearrange array so elements < pivot go left, > pivot go right
  • Recurse: Recursively apply to left and right subarrays
  • Combine: No need to combine as array is sorted in place

Key Characteristics:

  • In-place algorithm (uses only O(log n) additional memory for recursion)
  • Not stable (may change order of equal elements)
  • Time complexity: O(n log n) average case, O(n²) worst case (already sorted)
  • Often faster in practice than other O(n log n) algorithms

Insertion Sort

Worst Case: O(n²)
Best Case: O(n)
Space Complexity: O(1)
Stable: Yes
0
Steps
0
Comparisons
0
Swaps
0ms
Time
Normal
Comparing
Swapping
Sorted
Current Element

Algorithm Code

function insertionSort(arr) {
  let n = arr.length;
  
  for (let i = 1; i < n; i++) {
    // Element to be inserted
    let key = arr[i];
    let j = i - 1;
    
    // Move elements greater than key one position ahead
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    
    // Insert key at correct position
    arr[j + 1] = key;
  }
  
  return arr;
}

How Insertion Sort Works

Insertion Sort builds the final sorted array one element at a time by repeatedly taking the next element and inserting it into its correct position in the already sorted part.

  • Start with first element: Consider it already sorted
  • Take next element: Insert it into correct position in sorted portion
  • Shift elements: Move larger elements one position to the right
  • Repeat: Continue until all elements are inserted

Key Characteristics:

  • In-place algorithm (uses only a constant amount of extra memory)
  • Stable (preserves order of equal elements)
  • Time complexity: O(n²) in worst and average cases, O(n) in best case (already sorted)
  • Efficient for small datasets or nearly sorted data