Merge Sort in Java

📚 Definition

Merge Sort is a divide-and-conquer algorithm used for sorting. It divides the input array into two halves, recursively sorts each half, and then merges the sorted halves.

📜 History and Background

Merge Sort was invented by John von Neumann in 1945. It's one of the earliest sorting algorithms and is known for its efficiency and stability. Its guaranteed $O(n \log n)$ time complexity makes it highly valuable in various applications.

🔑 Key Principles

• ➗ Divide: The array is divided into two halves until each sub-array contains only one element.
• ✨ Conquer: Each sub-array with a single element is inherently sorted.
• 🤝 Combine: The sorted sub-arrays are merged to produce new sorted sub-arrays until the entire array is sorted.

💻 Java Implementation

Here's a Java implementation of Merge Sort:

public class MergeSort {

    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++;
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};

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

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

        System.out.println("\nSorted array:");
        printArray(arr);
    }

    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
}

⏱️ Timing Merge Sort

To time the execution of Merge Sort, you can use the System.nanoTime() method in Java:

long startTime = System.nanoTime();
mergeSort(arr, 0, arr.length - 1);
long endTime = System.nanoTime();

long duration = (endTime - startTime);
System.out.println("Execution time: " + duration + " nanoseconds");

📊 Real-world Examples

• 🗂️ Database Systems: Used for sorting large datasets in databases.
• 🧬 Bioinformatics: Applied in genome sequencing and alignment algorithms.
• 📈 Data Analysis: Utilized for sorting data in statistical analysis and machine learning.

💡 Tips for Optimization

• ⚙️ Use Iterative Approach: For very large datasets, an iterative approach might reduce overhead.
• 🧠 Hybrid Approaches: Combine Merge Sort with other algorithms like Insertion Sort for smaller sub-arrays to improve performance.

Conclusion

Merge Sort is a powerful and efficient sorting algorithm with a guaranteed time complexity of $O(n \log n)$. Its stability and predictability make it a valuable tool in various applications. Understanding its implementation and timing helps in optimizing its performance for specific use cases.