Mastering Algorithms

Merge Sort

Overview

Merge Sort is a divide-and-conquer sorting algorithm that divides the array into two halves, sorts them recursively, and then merges the sorted halves. It is one of the most efficient sorting algorithms with a guaranteed O(n log n) time complexity in all cases.

Merge Sort is stable, meaning it preserves the relative order of equal elements, and it's particularly well-suited for sorting linked lists and external sorting (sorting data too large to fit in memory).

How It Works

The algorithm follows these steps:

  1. Divide: Split the array into two halves
  2. Conquer: Recursively sort both halves
  3. Combine: Merge the two sorted halves into a single sorted array

The base case occurs when the array has 0 or 1 element, which is already sorted. The merge step combines two sorted arrays by comparing elements from both arrays and placing them in order.

Algorithm


MergeSort(arr):
    if length of arr <= 1:
        return arr
    
    mid = length of arr / 2
    left = MergeSort(first half of arr)
    right = MergeSort(second half of arr)
    
    return Merge(left, right)

Merge(left, right):
    result = []
    i = 0, j = 0
    
    while i < length of left and j < length of right:
        if left[i] <= right[j]:
            append left[i] to result
            i = i + 1
        else:
            append right[j] to result
            j = j + 1
    
    append remaining elements from left to result
    append remaining elements from right to result
    
    return result

Implementation


def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Complexity Analysis

  • Time Complexity: O(n log n) in all cases (best, average, and worst)
    • The divide step takes O(1)
    • Each recursive call processes half the array: O(log n) levels
    • Merging two arrays of size n/2 takes O(n) time
    • Total: O(n log n)
  • Space Complexity: O(n) - requires additional space for the temporary arrays during merging

Characteristics

  • Stable: Yes - maintains relative order of equal elements
  • In-place: No - requires O(n) extra space
  • Adaptive: No - always performs the same operations regardless of input
  • Online: No - requires the entire array to be present

When to Use Merge Sort

Merge Sort is an excellent choice when:

  • You need guaranteed O(n log n) performance regardless of input
  • Stable sorting is required (preserving order of equal elements)
  • Sorting linked lists (can be implemented without extra space for linked lists)
  • External sorting (sorting data that doesn't fit in memory)
  • You need a predictable, consistent sorting algorithm

Example

Sorting [38, 27, 43, 3, 9, 82, 10]: 

Divide:
[38, 27, 43, 3, 9, 82, 10]
[38, 27, 43] [3, 9, 82, 10]
[38] [27, 43] [3, 9] [82, 10]
[38] [27] [43] [3] [9] [82] [10]

Merge:
[27, 38] [43] [3, 9] [10, 82]
[27, 38, 43] [3, 9, 10, 82]
[3, 9, 10, 27, 38, 43, 82]

Related Algorithms

Explore other sorting algorithms: