Sorting Algorithms — Merge Sort

Hi everyone! Welcome to my article on Sorting Algorithms part 5. In this blog, we’ll explore a most commonly used sorting algorithm; Merge Sort. Let’s dive in!

If you want to know the basics of Sorting Algorithms, you can check out my article on Sorting Algorithms part 1 — Introduction to Sorting Algorithms.

Concept

Merge Sort is an efficient, comparison-based, divide-and-conquer sorting algorithm. It works by dividing the array into smaller sub-arrays, sorting each sub-array, and then merging the sorted sub-arrays back together. This approach ensures that the array is sorted in a structured and systematic way.

Steps

1. Divide: Split the array into two halves.
2. Conquer: Recursively sort each half.
3. Merge: Merge the two sorted halves back together to form a single sorted array.

How Merge Sort Works

1. Splitting: Continuously split the array into halves until each sub-array contains a single element.
2. Merging: Merge the single-element sub-arrays back together in the correct order to produce sorted sub-arrays, and continue this process until the entire array is sorted.

Implementation

Here’s a simple Java implementation of Merge Sort:

public class MergeSort {

    // Method to merge two subarrays
    private static void merge(int[] array, int left, int middle, int right) {
        int n1 = middle - left + 1;
        int n2 = right - middle;

        // Create temporary arrays
        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];

        // Copy data to temporary arrays
        for (int i = 0; i < n1; ++i)
            leftArray[i] = array[left + i];
        for (int j = 0; j < n2; ++j)
            rightArray[j] = array[middle + 1 + j];

        // Merge the temporary arrays

        // Initial indexes of first and second subarrays
        int i = 0, j = 0;

        // Initial index of merged subarray
        int k = left;
        while (i < n1 && j < n2) {
            if (leftArray[i] <= rightArray[j]) {
                array[k] = leftArray[i];
                i++;
            } else {
                array[k] = rightArray[j];
                j++;
            }
            k++;
        }

        // Copy remaining elements of leftArray[]
        while (i < n1) {
            array[k] = leftArray[i];
            i++;
            k++;
        }

        // Copy remaining elements of rightArray[]
        while (j < n2) {
            array[k] = rightArray[j];
            j++;
            k++;
        }
    }

    // Method to sort array using Merge Sort
    public static void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            // Find the middle point
            int middle = (left + right) / 2;

            // Recursively sort first and second halves
            mergeSort(array, left, middle);
            mergeSort(array, middle + 1, right);

            // Merge the sorted halves
            merge(array, left, middle, right);
        }
    }

    // Main method to test the Merge Sort
    public static void main(String[] args) {
        int[] array = {12, 11, 13, 5, 6, 7};

        System.out.println("Unsorted array:");
        for (int num : array) {
            System.out.print(num + " ");
        }
        System.out.println();

        // Sort the array using Merge Sort
        mergeSort(array, 0, array.length - 1);

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

Explanation

1. Merge Function: The merge method merges two sub-arrays into a single sorted sub-array. It takes the array and the indices of the sub-arrays as parameters.
2. Merge Sort Function: The mergeSort method recursively divides the array into two halves, sorts each half, and then merges the sorted halves.
3. Main Method: The main method initializes an array, prints it, sorts it using Merge Sort, and then prints the sorted array.

Complexity of Merge Sort

Time Complexity

1. Best Case: O(nlog⁡n)
2. Average Case: O(nlog⁡n)
3. Worst Case: O(nlog⁡n)

• Merge Sort consistently performs at O(nlog⁡n) because it always divides the array in half and takes linear time to merge the halves.

Space Complexity: O(n)

• Merge Sort requires additional memory proportional to the size of the array because it uses temporary arrays to merge the sorted sub-arrays.

Summary

Merge Sort is an efficient, stable, and predictable sorting algorithm. It uses a divide-and-conquer approach to split the array into smaller sub-arrays, sort them, and merge them back together. It has a time complexity of O(nlog⁡n) and requires additional memory space for the temporary arrays.

I hope this blog has helped you understand the Merge Sort algorithm, its implementation and its complexity.

Thank you for reading! If you have any questions or feedback, feel free to leave a comment below. Happy coding!