Skip to content

Merge Sort

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 to produce the sorted array.

Algorithm Overview

The algorithm works by recursively dividing the array into smaller subarrays until each subarray has only one element, then merging these subarrays back together in sorted order.

Key Features

  • Divide and Conquer: Breaks problem into smaller subproblems
  • Stable: Maintains relative order of equal elements
  • Predictable Performance: Always O(n log n) regardless of input
  • Not In-Place: Requires additional memory for merging
  • Parallelizable: Subproblems can be solved independently

Time and Space Complexity

  • Time Complexity: O(n log n) in all cases (best, average, and worst)
  • Space Complexity: O(n) - requires additional space for merging
  • Recurrence: T(n) = 2T(n/2) + O(n)
  • Depth: log n levels of recursion

Algorithm Steps

  1. Divide: Split the array into two halves at the midpoint
  2. Conquer: Recursively sort both halves
  3. Combine: Merge the two sorted halves into a single sorted array
  4. Base Case: Arrays with 0 or 1 element are already sorted

Usage Examples

Basic Usage

from algo.algorithms.sorting.merge_sort import merge_sort

# Sort integers
numbers = [64, 34, 25, 12, 22, 11, 90]
sorted_numbers = merge_sort(numbers)
print(sorted_numbers)  # [11, 12, 22, 25, 34, 64, 90]

# Sort strings
words = ['banana', 'apple', 'cherry']
sorted_words = merge_sort(words)
print(sorted_words)  # ['apple', 'banana', 'cherry']

# Empty array
result = merge_sort([])
print(result)  # []

In-Place Sorting

from algo.algorithms.sorting.merge_sort import merge_sort_in_place

# Modify original array
arr = [64, 34, 25, 12]
merge_sort_in_place(arr)
print(arr)  # [12, 25, 34, 64]

Educational/Debugging

from algo.algorithms.sorting.merge_sort import merge_sort_verbose

# See step-by-step process
merge_sort_verbose([64, 34, 25, 12])

Output: 

Dividing: [64, 34, 25, 12]
  Left half: [64, 34]
  Right half: [25, 12]
Recursively sorting left half:
  Dividing: [64, 34]
    Left half: [64]
    Right half: [34]
  Recursively sorting left half:
    Base case: [64] (already sorted)
  Recursively sorting right half:
    Base case: [34] (already sorted)
  Merging [64] and [34]
    Merging process:
      Comparing 64 > 34: taking 34 from right
      Adding remaining 64 from left
  Merged result: [34, 64]
Recursively sorting right half:
  Dividing: [25, 12]
    Left half: [25]
    Right half: [12]
  Recursively sorting left half:
    Base case: [25] (already sorted)
  Recursively sorting right half:
    Base case: [12] (already sorted)
  Merging [25] and [12]
    Merging process:
      Comparing 25 > 12: taking 12 from right
      Adding remaining 25 from left
  Merged result: [12, 25]
Merging [34, 64] and [12, 25]
  Merging process:
    Comparing 34 > 12: taking 12 from right
    Comparing 34 > 25: taking 25 from right
    Comparing 34 <= 64: taking 34 from left
    Adding remaining 64 from left
Merged result: [12, 25, 34, 64]

Edge Cases Handled

# Empty array
result = merge_sort([])  # Returns []

# Single element
result = merge_sort([42])  # Returns [42]

# Already sorted
result = merge_sort([1, 2, 3, 4])  # Returns [1, 2, 3, 4]

# Reverse sorted
result = merge_sort([4, 3, 2, 1])  # Returns [1, 2, 3, 4]

# Duplicates
result = merge_sort([3, 1, 3, 1])  # Returns [1, 1, 3, 3]

API Reference

Merge Sort Algorithm Implementation

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 to produce the sorted array.

Time Complexity: O(n log n) in all cases (best, average, and worst)

Space Complexity: O(n) - requires additional space for merging

Stability: Stable (maintains relative order of equal elements)

merge_sort(arr)

Sort an array using the merge sort algorithm.

The algorithm works by recursively dividing the array into smaller subarrays until each subarray has only one element, then merging these subarrays back together in sorted order.

Parameters:

Name Type Description Default
arr List[T]

List of comparable elements to sort

 required

Returns:

Type Description
List[T]

A new sorted list (does not modify the original array)

Examples:

>>> merge_sort([64, 34, 25, 12, 22, 11, 90])
[11, 12, 22, 25, 34, 64, 90]

>>> merge_sort(['banana', 'apple', 'cherry'])
['apple', 'banana', 'cherry']

>>> merge_sort([])
[]

merge_sort_in_place(arr)

Sort an array using merge sort algorithm with in-place modification.

This version modifies the original array instead of creating a new one.

Parameters:

Name Type Description Default
arr List[T]

List of comparable elements to sort

 required

Returns:

Type Description
List[T]

The sorted list (same object as input, modified in-place)

merge_sort_verbose(arr, depth=0)

Merge sort with detailed step-by-step output for educational purposes.

This version prints each step of the divide-and-conquer process to help understand how the algorithm works.

Parameters:

Name Type Description Default
arr List[T]

List of comparable elements to sort

 required
depth int

Current recursion depth (for indentation)

 0

Returns:

Type Description
List[T]

A new sorted list