We’re doing it with arrays in Java — no fancy lists, no magic. Just clean, recursive, efficient sorting vibes.

---

🔀 Merge Sort (Array Implementation in Java)

“Why fight the whole battle at once, when you can break it down, conquer each part, then unite like the Avengers?”
— Merge Sort, probably

---

🧠 What is Merge Sort?

Merge Sort is a Divide and Conquer algorithm that:

1. Divides the array into halves

2. Recursively sorts both halves

3. Merges the sorted halves into a single sorted array

It’s recursive. It’s elegant. And it’s got a consistent time complexity of O(n log n) — even in the worst case. 💪

---

🔢 Time & Space Complexity

---

🔧 Merge Sort in Java (Array Version)

Here it is. Fully functional. No imports. Pure Java array goodness.

java
CopyEdit
public class MergeSort {

    // Public method to sort the array
    public void sort(int[] array) {
        if (array == null || array.length < 2) return;
        mergeSort(array, 0, array.length - 1);
    }

    // Recursive merge sort
    private void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;

            // Recursively sort both halves
            mergeSort(array, left, mid);
            mergeSort(array, mid + 1, right);

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

    // Merge two sorted subarrays: [left..mid] and [mid+1..right]
    private void merge(int[] array, int left, int mid, int right) {
        // Sizes of the two subarrays
        int n1 = mid - left + 1;
        int n2 = right - mid;

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

        // Copy data
        for (int i = 0; i < n1; i++)
            L[i] = array[left + i];
        for (int j = 0; j < n2; j++)
            R[j] = array[mid + 1 + j];

        // Merge the temp arrays back into original
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                array[k++] = L[i++];
            } else {
                array[k++] = R[j++];
            }
        }

        // Copy remaining elements, if any
        while (i < n1) {
            array[k++] = L[i++];
        }
        while (j < n2) {
            array[k++] = R[j++];
        }
    }

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

        MergeSort sorter = new MergeSort();
        sorter.sort(arr);

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

---

🔍 What’s Happening Here?

• 🧠 mergeSort() → recursive method that splits the array until it reaches subarrays of size 1

• 🧪 merge() → merges two sorted arrays into one sorted array

• 💾 Temporary arrays are created to hold the left and right halves (space complexity tradeoff)

---

💡 Why Merge Sort Slaps

• ✅ Stable sort (doesn’t change relative order of equal elements)

• ✅ Predictable O(n log n) time

• ✅ Great for large datasets

• ✅ Used in external sorting (e.g., sorting huge files on disk)

---

⚠️ Things to Watch Out For

• Not in-place → needs O(n) space

• Recursive → watch the stack depth for huge arrays

• Performance-wise, quick sort may beat it in practice (in-place), but merge sort has guaranteed time

---

🎓 TL;DR (Too Long, Didn’t Merge)

• Merge Sort uses Divide and Conquer

• Splits array → recursively sorts → merges it back

• Java array implementation needs helper function & temp arrays

• Worst-case time: O(n log n)

• Best-case time: O(n log n)

• Stable, consistent, and super useful for large-scale sorted problems

---

🧠 Final Thoughts

Merge Sort is the professor-approved, always-reliable choice in your sorting toolkit.
Whether you're prepping for interviews, optimizing regression data, or just trying not to use Arrays.sort() for once —
Merge Sort is your clean, logical, recursive bestie.