Merge Sort - Data Structures and Algorithms (DSA) Guide

Table of Contents 📚

Introduction to Merge Sort
How Does Merge Sort Work?
Basic Implementation
Space Efficient Implementation with Auxiliary Array
Time and Space Complexity
Conclusion

🌟 Introduction to Merge Sort

Merge Sort is one of the most efficient sorting algorithms, and it plays a fundamental role in computer science. This guide aims to give you a thorough understanding of how Merge Sort works and how to implement it in Java.

🌈 How Does Merge Sort Work?

Merge Sort is a classic example of a ‘divide and conquer’ algorithm. The primary idea behind it is to divide the original array into smaller arrays until each smaller array has only one position and then merge these smaller arrays in a sorted manner.

For instance, consider the array [3, 1, 4, 1, 5, 9, 2, 6, 5]. The algorithm would work as follows:

Divide the array into two halves.
- First Half: [3, 1, 4, 1]
- Second Half: [5, 9, 2, 6, 5]
Recursively sort each half.
- Sorted First Half: [1, 1, 3, 4]
- Sorted Second Half: [2, 5, 5, 6, 9]
Merge the sorted halves to produce a single sorted array.
- Sorted Array: [1, 1, 2, 3, 4, 5, 5, 6, 9]

🖥️ Basic Implementation of Merge Sort in Java

Here is the Java code for Basic Merge Sort which usage temporary arrays during merge phase:

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {3, 1, 4, 1, 5, 9, 2, 6, 5};
        mergeSort(arr, 0, arr.length - 1);

        for (int num : arr) {
            System.out.print(num + " ");
        }
    }

    public static void mergeSort(int[] arr, int l, int r) {
        if (l < r) {
            int m = l + (r - l) / 2;

            mergeSort(arr, l, m);
            mergeSort(arr, m + 1, r);

            merge(arr, l, m, r);
        }
    }

    public static void merge(int[] arr, int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;

        int[] L = new int[n1];
        int[] R = new int[n2];

        for (int i = 0; i < n1; ++i) {
            L[i] = arr[l + i];
        }
        for (int j = 0; j < n2; ++j) {
            R[j] = arr[m + 1 + j];
        }

        int i = 0, j = 0, k = l;
        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++;
        }
    }
}

🖥️ Space Efficient Merge Sort Implementation with Auxiliary Array

In this version, we use a single auxiliary array that is allocated once and used for merging throughout the sorting process. This saves us from the overhead of repeatedly allocating and de-allocating arrays at each level of recursion.

public class EfficientMergeSort {
    public static void main(String[] args) {
        int[] arr = {3, 1, 4, 1, 5, 9, 2, 6, 5};
        int[] aux = new int[arr.length];  // Auxiliary array
        mergeSort(arr, aux, 0, arr.length - 1);

        for (int num : arr) {
            System.out.print(num + " ");
        }
    }

    public static void mergeSort(int[] arr, int[] aux, int l, int r) {
        if (l < r) {
            int m = l + (r - l) / 2;

            mergeSort(arr, aux, l, m);
            mergeSort(arr, aux, m + 1, r);

            merge(arr, aux, l, m, r);
        }
    }

    public static void merge(int[] arr, int[] aux, int l, int m, int r) {
        // Copy data to the auxiliary array
        for (int k = l; k <= r; k++) {
            aux[k] = arr[k];
        }

        int i = l, j = m + 1, k = l;
        while (i <= m && j <= r) {
            if (aux[i] <= aux[j]) {
                arr[k] = aux[i];
                i++;
            } else {
                arr[k] = aux[j];
                j++;
            }
            k++;
        }

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

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

⏲️ Time and Space Complexity of Merge Sort

Time Complexity: Merge Sort always takes O(nlogn) time, irrespective of the arrangement of the elements in the initial array.
Space Complexity: Merge Sort requires O(n) additional space for the L and R arrays.

🎓 Conclusion

Merge Sort is an incredibly efficient and reliable sorting algorithm. While it may look complex at first, the divide and conquer strategy makes it highly efficient for large datasets.

Using an auxiliary array in Merge Sort can optimize memory usage without sacrificing speed. It offers a more practical approach, especially when working with large arrays.

If you find this guide useful, please share with others, and spread the knowledge!