Prologue

Sorting is one of the most essential operation in computer science. Whether it’s arranging numbers, organizing records in a database, or optimizing search operations, sorting plays a key role in improving efficiency.

Among many sorting algorithms like quick sort, bubble sort we will today talk about merge sort, that stands out for its consistency, stability and guaranteed performance. It follows divide and conquer paradigm.

Algorithm

Merge sort works by repeatedly dividing the array into two halves and then sorting the two halves and merging the sorted halves.

1. Begin by dividing the unsorted array into two smaller sub-arrays, each half the size of the original.

2. Continue dividing these sub-arrays until each piece contains only one element.

3. Carefully merge the sub-arrays by consistently placing the lowest value first i.e. sort the array.

4. Persist in merging until all sub-arrays are combined into a single, sorted array.

Implementation in JAVA

public class MergeSort {

    // Function to divide the array into halves
    void divide(int arr[], int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;

            // Divide further
            divide(arr, left, mid);
            divide(arr, mid + 1, right);

            // After dividing, sort and merge
            sortAndMerge(arr, left, mid, right);
        }
    }

    // Function to sort and merge two halves
    void sortAndMerge(int arr[], int left, int mid, int right) {
        // Sizes of two subarrays
        int n1 = mid - left + 1;
        int n2 = right - mid;

        // Temporary arrays
        int L[] = new int[n1];
        int R[] = new int[n2];

        // Copy data
        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 step
        mergeBack(arr, L, R, left);
    }

    // Function to merge back into original array
    void mergeBack(int arr[], int L[], int R[], int start) {
        int i = 0, j = 0, k = start;

        // Merge two sorted arrays
        while (i < L.length && j < R.length) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        // Copy remaining elements of L[]
        while (i < L.length) {
            arr[k] = L[i];
            i++;
            k++;
        }

        // Copy remaining elements of R[]
        while (j < R.length) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    // Main Function
    public static void main(String args[]) {
        int arr[] = {38, 27, 43, 3, 9, 82, 10};

        System.out.println("Original Array:");
        for (int num : arr) System.out.print(num + " ");
        System.out.println();

        MergeSort ms = new MergeSort();
        ms.divide(arr, 0, arr.length - 1);

        System.out.println("Sorted Array:");
        for (int num : arr) System.out.print(num + " ");
    }
}

Output:

Time Complexity

Comparison between Merge Sort and Quick sort

Advantages of Merge Sort

• Consistent Time Complexity

• Stable Sorting Algorithm

• Good for Large Datasets

• Divide and Conquer

Limitation of Merge Sort

• Extra Space Requirement

• Overhead for Small Arrays

  • Overhead refers to the extra work or extra cost an algorithm has to perform in addition to its main task.

• Uses recursion, which increases the function call overhead and may cause stack overflow for very large arrays if not optimized.

Conclusion

Merge Sort is a robust divide and conquer algorithm known for its consistent time complexity of O(n log n) in all scenarios. It ensures stability, which is crucial when the order of equal elements is important. Its dependability and efficiency in managing large datasets, particularly in external sorting and linked lists, make it a favored option in various situations.

Nonetheless, its extra space requirement (O(n)) and recursion overhead can make it less suitable for smaller datasets compared to simpler algorithms like Insertion Sort. Furthermore, since it is not in-place, it may not be the best choice when memory resources are limited.