Merge Sort

Why did the merge sort algorithm become a marriage counselor? Because it was an expert at bringing two halves together for a harmonious union!

What is Merge Sort?

Merge Sort is a highly efficient and widely used comparison-based sorting algorithm. It follows the divide-and-conquer strategy to sort an array or list of elements. Merge Sort divides the array into smaller subarrays, sorts each subarray, and then combines (merges) them to produce a fully sorted array. It is known for its stable sorting behavior and consistent performance.

How it Works

Here's a step-by-step explanation of how Merge Sort works:

1. Divide: The input array is divided into two equal (or nearly equal) subarrays until each subarray contains only one element. This is achieved recursively.

2. Conquer: Each subarray is sorted independently. This is typically done using a recursive call to Merge Sort.

3. Merge: The sorted subarrays are merged to create larger sorted subarrays until the entire array is sorted. The merging process ensures that the elements are compared and combined in the correct order.

The merging process is the key to Merge Sort's efficiency. It involves comparing elements from both subarrays and placing them in the correct order in the merged subarray. This step is repeated until all elements are merged.

Merge Sort Code in Java:

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};

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

        System.out.println("Sorted array:");
        for (int value : arr) {
            System.out.print(value + " ");
        }
    }

    public static void mergeSort(int arr[], int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;

            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

            merge(arr, left, mid, right);
        }
    }

    public static void merge(int arr[], int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];

        for (int i = 0; i < n1; i++) {
            leftArray[i] = arr[left + i];
        }
        for (int j = 0; j < n2; j++) {
            rightArray[j] = arr[mid + 1 + j];
        }

        int i = 0, j = 0, k = left;

        while (i < n1 && j < n2) {
            if (leftArray[i] <= rightArray[j]) {
                arr[k] = leftArray[i];
                i++;
            } else {
                arr[k] = rightArray[j];
                j++;
            }
            k++;
        }

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

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

Merge Sort Code in C:

#include <stdio.h>

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int leftArray[n1], rightArray[n2];

    for (int i = 0; i < n1; i++) {
        leftArray[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        rightArray[j] = arr[mid + 1 + j];
    }

    int i = 0, j = 0, k = left;

    while (i < n1 && j < n2) {
        if (leftArray[i] <= rightArray[j]) {
            arr[k] = leftArray[i];
            i++;
        } else {
            arr[k] = rightArray[j];
            j++;
        }
        k++;
    }

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

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

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

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    mergeSort(arr, 0, n - 1);

    printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

Time and Space Complexity Analysis

The time complexity of Merge Sort can be expressed mathematically as follows:

Let n be the number of elements in the array to be sorted.

Merge Sort follows a divide-and-conquer approach:

1. Divide: The array is divided into two equal-sized (or nearly equal-sized) subarrays.

2. Conquer: Each subarray is sorted independently using Merge Sort recursively.

3. Merge: The sorted subarrays are merged to produce a single sorted array.

Here's how we can mathematically analyze the time complexity:

• In each level of recursion, the array is divided into two subarrays of roughly equal size. This division continues until each subarray contains only one element, which takes log₂(n) levels of recursion because you're effectively halving the array size at each level.

• At each level of recursion, the merging step takes O(n) time because it involves comparing and merging all the elements in the subarrays.

• Since there are log₂(n) levels of recursion and each level takes O(n) time for merging, the total time complexity is O(n log n).

Mathematically, this can be expressed as:

$$(T(n) = 2 \cdot T\left(\frac{n}{2}\right) + O(n))$$

Using the Master Theorem or by analyzing the recurrence relation, you can determine that the time complexity of Merge Sort is O(n log n).

This makes Merge Sort highly efficient and it maintains this efficiency regardless of the initial order of the elements, making it a preferred choice for sorting large datasets in practice.

The Space Complexity is: O(n) (additional memory required for temporary arrays in the merge step)

Merge Sort consistently achieves a time complexity of O(n log n), which makes it one of the most efficient sorting algorithms, even for large datasets. Its stable sorting behavior and efficient use of memory (O(n)) for temporary storage make it a preferred choice for various sorting applications.