Merge Sort

Merge Sort is a divide-and-conquer algorithm that divides the array into halves, sorts them recursively, and then merges the sorted halves. It has consistent O(n log n) performance and is stable.

Merge Sort Visualization

Complexity

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

Pseudocode

function MergeSort(array):
  if length(array) <= 1:
    return array
  
  mid = length(array) / 2
  left = MergeSort(array[0..mid])
  right = MergeSort(array[mid..end])
  
  return Merge(left, right)

Related Algorithms

Quick Sort

Quick Sort is a divide-and-conquer algorithm that picks a pivot element and partitions the array around it. It&apos;s one of the fastest sorting algorithms in practice, though worst-case performance is O(n²).

Time: O(n log n) average, O(n²) worst | Space: O(log n)