AV
LibraryMerge Sort

Merge Sort

Medium

Merge Sort is a divide-and-conquer algorithm that divides the input list into halves, sorts them recursively, and then merges them back together. It guarantees O(n log n) time complexity.

Time Complexity

O(n log n)

Space Complexity

O(n)

Category

Sorting

Introduction to Merge Sort

Merge Sort is a highly efficient sorting algorithm that uses the divide-and-conquer paradigm. It's one of the most important algorithms in computer science and forms the basis for external sorting and many database operations.

How It Works

The algorithm works in two phases:

**Divide Phase**:

1. Divide the array into two halves

2. Recursively divide each half until you have single elements

3. Continue until the entire array is divided

**Conquer/Merge Phase**:

1. Compare elements from both halves

2. Pick the smaller element and add to result array

3. Move the pointer of the array from which element was taken

4. Repeat until all elements are merged

Algorithm Complexity

**Time Complexity**: O(n log n) - Dividing takes O(log n) and merging takes O(n)
**Space Complexity**: O(n) - Requires temporary arrays for merging

Best and Worst Cases

**Best Case**: O(n log n) - Even if array is sorted
**Worst Case**: O(n log n) - Consistent performance
**Average Case**: O(n log n) - For random data

Advantages

1. Guaranteed O(n log n) performance

2. Stable sorting algorithm

3. Predictable behavior

4. Good for linked lists

5. Suitable for external sorting (large datasets on disk)

Disadvantages

1. Requires O(n) extra space

2. Not in-place sorting

3. Higher constant factors than quicksort

4. Slower for small arrays due to overhead

When to Use

**Large datasets**: Excellent for sorting millions of elements
**Linked lists**: More efficient than quicksort for linked lists
**External sorting**: Ideal for sorting data larger than RAM
**Stable sorting requirement**: When maintaining order of equal elements is important
**Predictable performance**: When worst-case guarantee is critical

Comparison with Quicksort

Merge Sort: O(n log n) guaranteed, requires O(n) space
Quick Sort: O(n²) worst case, but usually faster with O(log n) space
Merge Sort is more predictable, Quicksort usually faster in practice

Applications

External sorting
Counting inversions
Creating sorted databases
Parallel sorting
Merge operations in databases

Key Takeaways

  • Divide-and-conquer approach
  • Stable sorting
  • Requires additional space
  • Consistent performance
  • Suitable for large datasets
  • Widely used in practice

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) {
  const result = [];
  while (left.length && right.length) {
    if (left[0] <= right[0]) result.push(left.shift());
    else result.push(right.shift());
  }
  return [...result, ...left, ...right];
}

Tags

sortingdivide-and-conquerstableintermediate

Quick Stats

Difficulty:Medium
Type:Sorting

Share