Implementing Merge Sort in Java

By
Shivam Gupta
-
15
Implementing Merge Sort in Java
Advertisement

Implementing Merge Sort in Java

Merge Sort is a powerful and efficient sorting algorithm based on the divide-and-conquer technique. In this blog post, we’ll delve into the Implementing Merge Sort in Java, understand its algorithmic approach. Let’s explore how Merge Sort achieves a time complexity of O(n log n) and provides a stable and consistent performance.

Understanding the Divide-and-Conquer Approach:

Merge Sort operates on the principle of divide and conquer, breaking down a problem into smaller sub-problems until they become trivial to solve. The algorithm then combines the solutions of the sub-problems to solve the original problem. In the case of sorting, Merge Sort recursively divides an array into halves until each sub-array contains only one element. It then merges these sorted sub-arrays to produce a fully sorted array.

Steps:

Divide:

  • Divide the unsorted array into two halves.

Conquer:

  • Recursively apply Merge Sort to each of the sub-arrays.

Combine:

  • Merge the two sorted sub-arrays into a single sorted array.

Merge Sort Implementation in Java:

Java Program – Merge Sort
public class Main {

    // Main method to sort the array using merge sort
    public static void sort(int[] array) {
        if (array == null || array.length <= 1) {
            return; // Already sorted or empty array
        }

        // Call the mergeSort method to start the sorting process
        mergeSort(array, 0, array.length - 1);
    }

    // Recursive method to divide the array and merge the sorted halves
    private static void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            // Find the middle point to divide the array into two halves
            int mid = left + (right - left) / 2;

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

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

    // Merge method to combine two sorted halves into a single sorted array
    private static void merge(int[] array, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        // Create temporary arrays to store the left and right halves
        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];

        // Copy data to temporary arrays
        System.arraycopy(array, left, leftArray, 0, n1);
        System.arraycopy(array, mid + 1, rightArray, 0, n2);

        // Merge the two halves
        int i = 0, j = 0, k = left;

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

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

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

    // Helper method to print an array
    public static void printArray(int[] array) {
        for (int value : array) {
            System.out.print(value + " ");
        }
        System.out.println();
    }

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

        System.out.println("Original Array:");
        printArray(array);

        sort(array);

        System.out.println("Sorted Array:");
        printArray(array);
    }
}

Explanation:

  1. sort Method:
    • This is the entry point to the Merge Sort algorithm. It checks if the array is null or has only one element (already sorted), and then calls mergeSort to begin the sorting process.
  2. mergeSort Method:
    • The recursive method that divides the array into halves until each sub-array contains one element. It then calls the merge method to merge the sorted sub-arrays.
  3. merge Method:
    • Merges two sorted halves (leftArray and rightArray) into a single sorted array (array).
    • Uses three pointers (i, j, and k) to iterate through the left, right, and merged arrays.
  4. printArray Method:
    • A helper method to print the contents of an array.

Example:

Consider the array {38, 27, 43, 3, 9, 82, 10}.

  1. Initial Step:
    • Array: {38, 27, 43, 3, 9, 82, 10}.
  2. Recursive Steps:
    • {38, 27, 43} and {3, 9, 82, 10}.
    • Further divisions until each sub-array has one element.
  3. Merging Steps:
    • Merge sorted sub-arrays into larger sorted arrays.
  4. Final Sorted Array:
    • {3, 9, 10, 27, 38, 43, 82}.

This example illustrates how Merge Sort recursively divides and conquers the array, ultimately producing a fully sorted result.

Output:

Output – Merge Sort
Original Array:
38 27 43 3 9 82 10 
Sorted Array:
3 9 10 27 38 43 82

Advantages of Merge Sort:

  • Stable Sorting: Maintains the relative order of equal elements.
  • Predictable Performance: Consistently performs at O(n log n), making it suitable for large datasets.
  • External Sorting: Can efficiently handle large datasets stored on external storage devices.
ComplexityWorst CaseAverage CaseBest Case
Time ComplexityO(n log n)O(n log n)O(n log n)
Space ComplexityO(n) auxiliaryO(n) auxiliaryO(n) auxiliary

Conclusion:

Merge Sort stands as a testament to the elegance and efficiency of divide-and-conquer algorithms. Its ability to consistently deliver a stable and optimal performance makes it a reliable choice for a variety of applications. In Java, the implementation is concise yet powerful, showcasing the beauty of the algorithm. As you delve deeper into the world of sorting algorithms, Merge Sort undoubtedly earns its place as a fundamental and reliable tool in the programmer’s toolkit.

Latest Posts:

RELATED ARTICLESMORE FROM AUTHOR