On this page & study actions

Assessed progress

Learning resources

Merge Sort Visualizer

Practice this topic Next topicQuick Sort Algorithm

Unit 2: Divide & Conquer5 min read

Merge Sort Algorithm

The Merge Sort algorithm is an efficient, comparison-based sorting algorithm. It is a prime example of the Divide and Conquer algorithmic paradigm, offering a reliable $O(N \log N)$ time complexity across all cases, making it highly valuable for sorting large datasets.

1. Understanding Divide and Conquer

The Divide and Conquer paradigm is a powerful problem-solving strategy that involves three main steps:

Divide: Break the problem into two or more smaller subproblems that are instances of the same type as the original problem. These subproblems are typically smaller in size.
Conquer: Solve the subproblems recursively. If the subproblem is small enough (base case), solve it directly.
Combine: Combine the solutions of the subproblems to form the solution for the original problem.

This approach often leads to recursive algorithms. The time complexity of many divide-and-conquer algorithms is given by recurrence relations of the form:

T(n) = aT(n/b) + f(n)

Where $T(n)$ is the time to solve a problem of size $n$ , $a$ is the number of subproblems, $n/b$ is the size of each subproblem, and $f(n)$ is the time to divide the problem and combine the subproblem solutions.

2. Merge Sort: The Algorithm

Merge Sort applies the divide and conquer strategy to the sorting problem. Given an unsorted array of $N$ elements, the goal is to sort them in non-decreasing order.

2.1 Divide Phase

The array A[p...r] is divided into two sub-arrays: A[p...q] and A[q+1...r], where $q$ is the midpoint of the array, typically $q = \lfloor (p+r)/2 \rfloor$ . This division continues recursively until sub-arrays contain only one element. A single-element array is inherently sorted, forming the base case for the recursion.

2.2 Conquer Phase

Each of the two sub-arrays is sorted recursively using Merge Sort itself. This means calling mergeSort on A[p...q] and mergeSort on A[q+1...r].

2.3 Combine Phase (Merging)

This is the crucial step where two sorted sub-arrays are merged into a single, larger sorted array. This process involves comparing elements from the two sub-arrays and placing them into a temporary auxiliary array in sorted order. Once all elements are placed, the sorted auxiliary array is copied back into the original array segment.

Consider two sorted sub-arrays L and R. The merging process works as follows:

Maintain three pointers: i for L, j for R, and k for the merged output array.
Compare L[i] and R[j]. The smaller element is placed into arr[k], and its respective pointer (i or j) is incremented, along with k.
If one sub-array runs out of elements, copy the remaining elements from the other sub-array directly into the output array.

This merge operation takes $O(N)$ time, where $N$ is the total number of elements in the two sub-arrays being merged.

3. Step-by-Step Example

Let's sort the array [8, 2, 9, 4, 5, 3, 1, 6] using Merge Sort:

text

Input: [8, 2, 9, 4, 5, 3, 1, 6]
        /           \
      [8, 2, 9, 4]   [5, 3, 1, 6]   (Divide into halves)
      /     \         /     \
    [8, 2] [9, 4]    [5, 3] [1, 6] (Further divide)
    /  \   /  \     /  \   /  \
  [8] [2] [9] [4] [5] [3] [1] [6]  (Base cases: single elements are sorted)
    \  /   \  /     \  /   \  /
    [2, 8] [4, 9]    [3, 5] [1, 6]  (Merge sorted pairs: (8,2)->(2,8), (9,4)->(4,9) etc.)
      \     /         \     /
      [2, 4, 8, 9]   [1, 3, 5, 6]   (Merge sorted halves: (2,8,4,9)->(2,4,8,9), (3,5,1,6)->(1,3,5,6))
        \           /
      [1, 2, 3, 4, 5, 6, 8, 9]    (Final merged sorted array)

4. C++ Implementation

Here's a C++ implementation of the Merge Sort algorithm:

cpp

#include <iostream>
#include <vector>
#include <algorithm> // Not strictly needed for this basic implementation, but useful for other operations
 
// Function to merge two sorted sub-arrays
void merge(std::vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1; // Size of the first sub-array
    int n2 = right - mid;    // Size of the second sub-array
 
    // Create temporary arrays to hold the sub-arrays
    std::vector<int> L(n1);
    std::vector<int> R(n2);
 
    // Copy data from the main array to the temporary arrays
    for

5. Analysis of Merge Sort

5.1 Time Complexity

The time complexity of Merge Sort can be derived using a recurrence relation:

Divide: $O(1)$ to find the middle element.
Conquer: $2T(n/2)$ for recursively sorting two halves.
Combine: $O(n)$ for merging the two sorted halves.

Thus, the recurrence relation for Merge Sort is:

T(n) = 2T(n/2) + \Theta(n)

Applying the Master Theorem (Case 2, where $a=2$ , $b=2$ , and $f(n) = \Theta(n^{\log_b a}) = \Theta(n^{\log_2 2}) = \Theta(n)$ ), the solution is:

T(n) = \Theta(n \log n)

This $O(N \log N)$ complexity holds true for the best, average, and worst-case scenarios, which is a significant advantage over algorithms like Quick Sort (which can degrade to $O(N^2)$ in the worst case).

5.2 Space Complexity

Merge Sort requires an auxiliary array for the merging process. In the typical implementation, this temporary array has a size proportional to the input array size. Hence, its space complexity is $O(N)$ . This makes it not an in-place sorting algorithm.

5.3 Stability

Merge Sort is a stable sorting algorithm. This means that if two elements have equal values, their relative order in the input array is preserved in the sorted output. This property is particularly useful in scenarios where elements have associated data and their original order matters for equal keys. The L[i] <= R[j] comparison in the merge function ensures this stability.

5.4 Advantages and Disadvantages

Advantages:

Guaranteed $O(N \log N)$ performance: Consistent time complexity in all cases (best, average, worst).
Stable: Preserves the relative order of equal elements.
Suitable for large datasets: Its efficiency makes it a good choice for large inputs.
Works well with linked lists: Can be implemented without extra space complexity for linked lists as elements can be merged by changing pointers.
External sorting: Can sort data that doesn't fit into memory.

Disadvantages:

Requires $O(N)$ auxiliary space: This can be a concern for memory-constrained environments, making it less memory-efficient than in-place algorithms like Heap Sort or (average case) Quick Sort.
Slightly slower for small arrays: Due to the overhead of recursion and copying elements, it might be slower than insertion sort for very small arrays.

Summary

Merge Sort is a Divide and Conquer sorting algorithm.
It works by recursively dividing an array into two halves, sorting each half, and then merging the sorted halves.
Its time complexity is consistently $O(N \log N)$ in best, average, and worst cases.
It requires $O(N)$ auxiliary space for the merging process.
Merge Sort is a stable sorting algorithm, preserving the relative order of equal elements.
It is well-suited for large datasets and external sorting.

Assessed progress

Learning resources

Merge Sort Algorithm

Merge Sort Algorithm

1. Understanding Divide and Conquer

2. Merge Sort: The Algorithm

2.1 Divide Phase

2.2 Conquer Phase

2.3 Combine Phase (Merging)

3. Step-by-Step Example

4. C++ Implementation

5. Analysis of Merge Sort

5.1 Time Complexity

5.2 Space Complexity

5.3 Stability

5.4 Advantages and Disadvantages

Summary

Key Concepts

Divide and Conquer Paradigm

Recursion

Merging

Time Complexity O(N log N)

Stable Sort

Quick Check

Advanced Data Structures

Advanced Data Structures