Merge Sort: A Powerful Sorting Algorithm

Introduction

Imagine you have a pile of messy cards, and you want to sort them from smallest to largest. What if you split the pile into smaller piles, sorted each one, and then combined them back together in order? That’s exactly how Merge Sort works! Let’s learn about it in a fun and simple way.

History

Merge Sort was invented by John von Neumann in 1945. He was a genius mathematician and computer scientist who worked on some of the most important discoveries in computing and mathematics. Merge Sort is one of his contributions to the world of algorithms.

Time Complexity

Merge Sort is very efficient compared to other sorting algorithms:

Best Case: O(n log n)
Worst Case: O(n log n)
Average Case: O(n log n)

This means it works well even for large datasets, making it a popular choice for sorting.

How Does It Work?

Merge Sort uses a “divide and conquer” strategy. Here’s how it works:

Divide: Split the list into two smaller lists until each list has only one element.
Conquer: Sort the smaller lists.
Merge: Combine the sorted lists back together into one sorted list.

Example: Sorting [8, 4, 7, 2, 5, 1, 3, 6]

Split the list into smaller pieces: [8, 4, 7, 2] and [5, 1, 3, 6].
Split again: [8, 4], [7, 2], [5, 1], [3, 6].
Split further: [8], [4], [7], [2], [5], [1], [3], [6].
Sort each pair: [4, 8], [2, 7], [1, 5], [3, 6].
Merge sorted pairs: [2, 4, 7, 8], [1, 3, 5, 6].
Merge the final lists: [1, 2, 3, 4, 5, 6, 7, 8].

Example: Sort [6, 3, 8, 5, 2]

Split the Array:
- [6, 3, 8, 5, 2] becomes [6, 3, 8] and [5, 2].
- [6, 3, 8] becomes [6] and [3, 8].
- [3, 8] becomes [3] and [8].
- [5, 2] becomes [5] and [2].
Sort the Pieces:
- Merge [3] and [8] into [3, 8].
- Merge [5] and [2] into [2, 5].
- Merge [6] and [3, 8] into [3, 6, 8].
- Merge [3, 6, 8] and [2, 5] into [2, 3, 5, 6, 8].
Final Result: [2, 3, 5, 6, 8]

Pseudocode

Here’s the logic in simple pseudocode:

MergeSort(array):
    if size of array <= 1:
        return array

    mid = size of array / 2
    left = MergeSort(array[0..mid])
    right = MergeSort(array[mid+1..end])

    return Merge(left, right)

Merge(left, right):
    result = []
    while left and right are not empty:
        if left[0] <= right[0]:
            add left[0] to result
            remove left[0] from left
        else:
            add right[0] to result
            remove right[0] from right

    add remaining elements of left (if any) to result
    add remaining elements of right (if any) to result

    return result

C++ Code

Here’s how you can write Merge Sort in 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;

    vector<int> L(n1), R(n2);

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

    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++;
    }
}

void mergeSort(vector<int>& 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);
    }
}

void printArray(const vector<int>& arr) {
    for (int val : arr)
        cout << val << " ";
    cout << endl;
}

int main() {
    vector<int> arr = {12, 11, 13, 5, 6, 7};
    cout << "Original array: ";
    printArray(arr);

    mergeSort(arr, 0, arr.size() - 1);

    cout << "Sorted array: ";
    printArray(arr);

    return 0;
}

Summary

Merge Sort is a powerful algorithm that efficiently sorts even large datasets. Its “divide and conquer” approach makes it unique and reliable. Now that you understand Merge Sort, try using it in your own coding projects!

GeekJuggernaut