Merge Sort Algorithm

Generated on 2025-07-10 02:05:57 Algorithm Cheatsheet for Technical Interviews

---

Merge Sort Algorithm Cheatsheet

1. Quick Overview

• What is it? A divide-and-conquer sorting algorithm that recursively divides the array into smaller sub-arrays, sorts them individually, and then merges them back together in a sorted manner.
• When to use it?
  • When you need a stable sort (maintains the relative order of equal elements).
  • When guaranteed O(n log n) performance is crucial.
  • When the data is too large to fit in memory (external sorting). Merge sort can be adapted for reading and writing data in chunks.
• When not to use it?
  • When space is extremely limited (Merge sort requires extra space for merging).
  • When a simpler algorithm like insertion sort is sufficient for small datasets.
  • When data is nearly sorted and an adaptive algorithm like insertion sort or Timsort would perform better.

2. Time & Space Complexity

Metric	Value	Explanation
Time Complexity (Best)	O(n log n)	The array is always split into halves, and merging takes O(n) time.
Time Complexity (Average)	O(n log n)
Time Complexity (Worst)	O(n log n)
Space Complexity	O(n)	Requires auxiliary space of O(n) for merging. This is a significant drawback. In-place merge sort implementations exist, but they are complex and often inefficient.
Stability	Stable	Equal elements maintain their relative order.

3. Implementation

Python:

def merge_sort(arr):
    """
    Sorts an array using the Merge Sort algorithm.

    Args:
        arr: The array to be sorted.

    Returns:
        The sorted array.
    """
    if len(arr) <= 1:
        return arr  # Base case: Already sorted

    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    left = merge_sort(left)  # Recursive call on the left half
    right = merge_sort(right) # Recursive call on the right half

    return merge(left, right) # Merge the sorted halves

def merge(left, right):
    """
    Merges two sorted arrays into a single sorted array.

    Args:
        left: The sorted left array.
        right: The sorted right array.

    Returns:
        The merged sorted array.
    """
    merged = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  # Comparison and appending
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1

    # Append any remaining elements from either array
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

# Example Usage:
arr = [12, 11, 13, 5, 6, 7]
sorted_arr = merge_sort(arr)
print("Sorted array is:", sorted_arr) # Output: Sorted array is: [5, 6, 7, 11, 12, 13]
# Time Complexity: O(n log n)
# Space Complexity: O(n)

Java:

public class MergeSort {

    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return; // Base case: Already sorted
        }
        int[] aux = new int[arr.length]; // Auxiliary array for merging
        mergeSortHelper(arr, aux, 0, arr.length - 1);
    }

    private static void mergeSortHelper(int[] arr, int[] aux, int low, int high) {
        if (low < high) {
            int mid = low + (high - low) / 2; // Prevent potential integer overflow
            mergeSortHelper(arr, aux, low, mid);     // Recursive call on the left half
            mergeSortHelper(arr, aux, mid + 1, high); // Recursive call on the right half
            merge(arr, aux, low, mid, high);   // Merge the sorted halves
        }
    }

    private static void merge(int[] arr, int[] aux, int low, int mid, int high) {
        // Copy elements to the auxiliary array
        for (int i = low; i <= high; i++) {
            aux[i] = arr[i];
        }

        int i = low;    // Index for the left subarray
        int j = mid + 1; // Index for the right subarray
        int k = low;    // Index for the merged array

        while (i <= mid && j <= high) {
            if (aux[i] <= aux[j]) {
                arr[k] = aux[i];
                i++;
            } else {
                arr[k] = aux[j];
                j++;
            }
            k++;
        }

        // Copy any remaining elements from the left subarray
        while (i <= mid) {
            arr[k] = aux[i];
            i++;
            k++;
        }

        // Copy any remaining elements from the right subarray (optional, but good practice)
        while (j <= high) {
            arr[k] = aux[j];
            j++;
            k++;
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        mergeSort(arr);
        System.out.print("Sorted array is: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        // Output: Sorted array is: 5 6 7 11 12 13
    }
}
// Time Complexity: O(n log n)
// Space Complexity: O(n)

C++:

#include <iostream>
#include <vector>

using namespace std;

void merge(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // Create temporary vectors
    vector<int> L(n1);
    vector<int> R(n2);

    // Copy data to temporary vectors L[] and R[]
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    // Merge the temporary vectors back into arr[left..right]
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Copy the remaining elements of L[], if there are any
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // Copy the remaining elements of R[], if there are any
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        // Find the middle point
        int mid = left + (right - left) / 2; // Prevent integer overflow

        // Sort first and second halves
        mergeSort(arr, left, mid);        // Recursive call on the left half
        mergeSort(arr, mid + 1, right);   // Recursive call on the right half

        // Merge the sorted halves
        merge(arr, left, mid, right);
    }
}

int main() {
    vector<int> arr = {12, 11, 13, 5, 6, 7};
    mergeSort(arr, 0, arr.size() - 1);

    cout << "Sorted array is: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl; // Output: Sorted array is: 5 6 7 11 12 13
    return 0;
}
// Time Complexity: O(n log n)
// Space Complexity: O(n)

4. Common Patterns

• Bottom-Up Merge Sort (Iterative Merge Sort): Avoids recursion by merging pairs of elements, then pairs of pairs, and so on. Can sometimes be slightly more efficient than recursive merge sort.
• Merge Sort for Linked Lists: Adaptable for sorting linked lists because it doesn’t require random access.
• External Merge Sort: For sorting data sets too large to fit in memory. Data is read in chunks, sorted, and then merged.
• Counting Inversions: Merge sort is often used to count the number of inversions in an array. An inversion is a pair (i, j) such that i < j and arr[i] > arr[j]. During the merge step, each time an element from the right subarray is placed before an element from the left subarray, it indicates an inversion.

5. Pro Tips

• Optimization: Insertion Sort for Small Subarrays: When subarrays become small (e.g., size <= 15), switch to insertion sort. Insertion sort is efficient for small, nearly sorted arrays. This hybrid approach can improve overall performance.
• Pre-allocation of Auxiliary Array: Allocate the auxiliary array once at the beginning of the mergeSort function, instead of creating it in each recursive call. This reduces memory allocation overhead. (See the Java example).
• Early Termination: If the largest element in the left subarray is smaller than the smallest element in the right subarray, the array is already sorted. Skip the merge step in this case. This is a common optimization.
• Gotcha: Integer Overflow in Midpoint Calculation: When calculating the midpoint mid, use mid = low + (high - low) / 2 instead of mid = (low + high) / 2 to prevent potential integer overflow, especially when dealing with large arrays.
• Gotcha: Auxiliary Array Indexing: Be very careful with indexing when copying elements to and from the auxiliary array during the merge step. Off-by-one errors are common.

6. Practice Problems

1. LeetCode 148. Sort List: Sort a linked list in O(n log n) time using constant space complexity. (Requires in-place merge sort or other techniques).
2. LeetCode 493. Reverse Pairs: Given an array, find the number of reverse pairs (i, j) where i < j and nums[i] > 2 * nums[j]. Use merge sort to efficiently count these pairs.
3. LeetCode 315. Count of Smaller Numbers After Self: You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

7. Templates

C++ Template

#include <iostream>
#include <vector>

using namespace std;

template <typename T>
void merge(vector<T>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    vector<T> L(n1);
    vector<T> R(n2);

    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

template <typename T>
void mergeSort(vector<T>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

// Example usage
int main() {
    vector<int> arr = {12, 11, 13, 5, 6, 7};
    mergeSort(arr, 0, arr.size() - 1);

    cout << "Sorted array is: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

Python Template

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    left = merge_sort(left)
    right = merge_sort(right)

    return merge(left, right)

def merge(left, right):
    merged = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1

    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

# Example usage
arr = [12, 11, 13, 5, 6, 7]
sorted_arr = merge_sort(arr)
print("Sorted array is:", sorted_arr)

Java Template

public class MergeSortTemplate {

    public static <T extends Comparable<T>> void mergeSort(T[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        T[] aux = (T[]) new Comparable[arr.length];
        mergeSortHelper(arr, aux, 0, arr.length - 1);
    }

    private static <T extends Comparable<T>> void mergeSortHelper(T[] arr, T[] aux, int low, int high) {
        if (low < high) {
            int mid = low + (high - low) / 2;
            mergeSortHelper(arr, aux, low, mid);
            mergeSortHelper(arr, aux, mid + 1, high);
            merge(arr, aux, low, mid, high);
        }
    }

    private static <T extends Comparable<T>> void merge(T[] arr, T[] aux, int low, int mid, int high) {
        for (int i = low; i <= high; i++) {
            aux[i] = arr[i];
        }

        int i = low;
        int j = mid + 1;
        int k = low;

        while (i <= mid && j <= high) {
            if (aux[i].compareTo(aux[j]) <= 0) {
                arr[k] = aux[i];
                i++;
            } else {
                arr[k] = aux[j];
                j++;
            }
            k++;
        }

        while (i <= mid) {
            arr[k] = aux[i];
            i++;
            k++;
        }

        while (j <= high) {
            arr[k] = aux[j];
            j++;
            k++;
        }
    }

    public static void main(String[] args) {
        Integer[] arr = {12, 11, 13, 5, 6, 7};
        mergeSort(arr);
        System.out.print("Sorted array is: ");
        for (Integer num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}