Speed:

Merge Sort

Time: O(n log n)Space: O(n)Stable

🔄How Merge Sort Works

Merge Sort is a divide-and-conquer algorithm that recursively divides the array into smaller subarrays until each subarray contains only one element, then merges them back together in sorted order. It guarantees O(n log n) performance in all cases.

The algorithm follows three main steps:

Divide: Split the array into two halves recursively
Conquer: Sort the individual subarrays (base case: single elements)
Combine: Merge the sorted subarrays to produce the final sorted array

💻Implementation

// Merge Sort Implementation
function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  
  // Divide the array into two halves
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
  
  // Recursively sort both halves
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;
  
  // Compare elements from left and right arrays
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] <= right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }
  
  // Add remaining elements
  while (leftIndex < left.length) {
    result.push(left[leftIndex]);
    leftIndex++;
  }
  
  while (rightIndex < right.length) {
    result.push(right[rightIndex]);
    rightIndex++;
  }
  
  return result;
}

📊Algorithm Analysis

Time Complexity

• Best: O(n log n)
• Average: O(n log n)
• Worst: O(n log n)
• Recurrence: T(n) = 2T(n/2) + O(n)

Space & Properties

• Space: O(n) auxiliary space
• Stable: maintains relative order
• Not adaptive: always O(n log n)
• External: good for large datasets

✅ Advantages

• Guaranteed O(n log n) performance
• Stable sorting algorithm
• Predictable performance - no worst case degradation
• Parallelizable - can divide work across cores
• External sorting - works with large datasets

🎯 Best Use Cases

• Large datasets where stability matters
• External sorting (disk-based)
• Linked lists (no random access needed)
• Parallel processing environments
• When consistent performance is required