Merge Sort

Merge sort is a comparison-based sorting algorithm that follows a divide-and-conquer strategy. It operates by recursively breaking down a dataset into smaller subarrays, sorting those subarrays, and then merging them back together to produce a fully ordered result. Here’s a structured breakdown of its core principles:

---

Algorithm Overview

Core Strategy

1. Divide
   Recursively split the unsorted array into halves until reaching single-element subarrays (inherently sorted).

2. Conquer
   Sort adjacent subarrays through pairwise comparisons.

3. Merge
   Combine sorted subarrays by iteratively selecting the smallest elements until the full array is reconstructed.

---

Comparisson Table

Feature	Basic Implementation	Optimized Implementation
Space Complexity	O(n log n)	O(n)
Memory Allocations	Multiple (per recursion)	Single buffer
Best For	Conceptual clarity	Production environments
Drawback	Memory-heavy	Slightly complex indexing

---

🔄 Merge Process Visualization

graph TD
    A[3,7,2,5] --> B[3,7]
    A --> C[2,5]
    B --> D[3]
    B --> E[7]
    C --> F[2]
    C --> G[5]
    D --> H[3,7]
    E --> H
    F --> I[2,5]
    G --> I
    H --> J[2,3,5,7]
    I --> J

---

🧮 Implementations

Basic Implementation (Top-Down)

⚠️ Memory Considerations: Creates new ArrayLists at each split (not memory-optimal)

Java

MergeSort

public class MergeSort {
    public static void mergeSort(ArrayList<Integer> array) {
        int size = array.size();
        if (size < 2) {
            return;
        }

        int midIndex = size / 2;
        ArrayList<Integer> leftHalf = new ArrayList<>();
        ArrayList<Integer> rightHalf = new ArrayList<>();

        // Split array into left and right halves
        for (int i = 0; i < midIndex; i++) {
            leftHalf.add(array.get(i));
        }
        for (int i = midIndex; i < size; i++) {
            rightHalf.add(array.get(i));
        }

        // Recursively sort halves
        mergeSort(leftHalf);
        mergeSort(rightHalf);

        // Merge sorted halves back into original array
        merge(array, leftHalf, rightHalf);
    }

    private static void merge(ArrayList<Integer> array, ArrayList<Integer> leftHalf, ArrayList<Integer> rightHalf) {
        int leftSize = leftHalf.size();
        int rightSize = rightHalf.size();
        int i = 0, j = 0, k = 0;

        // Merge while both halves have elements
        while (i < leftSize && j < rightSize) {
            if (leftHalf.get(i) <= rightHalf.get(j)) {
                array.set(k, leftHalf.get(i));
                i++;
            } else {
                array.set(k, rightHalf.get(j));
                j++;
            }
            k++;
        }

        // Copy remaining left elements
        while (i < leftSize) {
            array.set(k, leftHalf.get(i));
            i++;
            k++;
        }

        // Copy remaining right elements
        while (j < rightSize) {
            array.set(k, rightHalf.get(j));
            j++;
            k++;
        }
    }
}

Key Properties

• 🔄 Stability: Preserves element order
• ⏱️ Time Complexity: O(n log n)
• 💾 Space Complexity: O(n log n)

Important Notes

• This is a top-down merge sort implementation
• Creates new ArrayLists for each split (not memory-optimal)
• Maintains stability by preserving equal elements' order
• Time complexity: O(n log n) in all cases
• Space complexity: O(n log n) due to recursive splitting

Optimized Implementation (Top-Down)

Java (Optimized)

OptimizedMergeSort

public class OptimizedMergeSort {
    public static void mergeSort(ArrayList<Integer> array) {
        if (array == null || array.size() < 2) return;

        // Single temporary buffer allocated once upfront
        ArrayList<Integer> temp = new ArrayList<>(array.size());
        for (int i = 0; i < array.size(); i++) {
            temp.add(0); // Initialize with dummy values
        }

        // Start recursive sorting with indices
        mergeSort(array, temp, 0, array.size() - 1);
    }

    private static void mergeSort(ArrayList<Integer> array, 
                                    ArrayList<Integer> temp, 
                                    int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(array, temp, left, mid);    // Sort left half
            mergeSort(array, temp, mid + 1, right); // Sort right half
            merge(array, temp, left, mid, right);  // Merge both halves
        }
    }

    private static void merge(ArrayList<Integer> array, 
                                ArrayList<Integer> temp, 
                                int left, int mid, int right) {
        // Copy both halves to the temporary buffer
        for (int i = left; i <= right; i++) {
            temp.set(i, array.get(i));
        }

        int i = left;       // Pointer for left half
        int j = mid + 1;    // Pointer for right half
        int k = left;       // Pointer for merged result

        // Merge back into original array
        while (i <= mid && j <= right) {
            if (temp.get(i) <= temp.get(j)) {
                array.set(k, temp.get(i));
                i++;
            } else {
                array.set(k, temp.get(j));
                j++;
            }
            k++;
        }

        // Copy remaining left half elements
        while (i <= mid) {
            array.set(k, temp.get(i));
            k++;
            i++;
        }
    }
}

Optimizations:

• Single Temporary Buffer:
  • Single ArrayList<Integer> temp is allocated once upfront.
  • Reused across all merge operations (no new allocations during recursion).
• Index-Based Sorting:
  • Works on sub-ranges of the original array using left/right indices.
  • Avoids splitting into new ArrayLists instances.
• In-Place Merging:
  • Uses the original array for merging results.
  • Temporary buffer only holds copies during merge phase.

Important Notes:

• This algorithm could be improved with the usage of primitive arrays (int[]) instead of ArrayList<Integer>.