Merge Sort – Sorting Algorithm

Merge Sort

Merge Sort is a stable, comparison-based sorting algorithm that uses the divide and conquer strategy. It divides the array into smaller subarrays, sorts them, and then merges them back together to produce a sorted array.

---

1. How It Works

1. Divide: Split the array into two halves.
2. Conquer: Recursively sort each half.
3. Merge: Combine the two sorted halves into one sorted array.

---

2. Characteristics

• Time Complexity:
  • Best/Average/Worst case: O(n log ⁡n)
• Space Complexity: O(n) (requires additional arrays for merging)
• Stable Sorting: Maintains the relative order of equal elements.

---

3. Example Process

Array: [38, 27, 43, 3, 9, 82, 10]

1. Divide: Split into [38, 27, 43, 3] and [9, 82, 10].
   • Further divide: [38], [27], [43], [3], [9], [82], [10].
2. Sort and Merge:
   • Merge [38] and [27] → [27, 38].
   • Merge [43] and [3] → [3, 43].
   • Merge [9] and [82] → [9, 82].
3. Final Merge:
   • Merge all subarrays to get [3, 9, 10, 27, 38, 43, 82].

---

4. Java Implementation

import java.util.Arrays;

public class MergeSort {
    // Merge two subarrays
    private static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1; // Size of left subarray
        int n2 = right - mid;    // Size of right subarray

        // 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] = arr[left + i];
        }
        for (int j = 0; j < n2; j++) {
            rightArray[j] = arr[mid + 1 + j];
        }

        // Merge the temporary arrays back into the original array
        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++;
        }

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

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

    // Main function for Merge Sort
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2; // Avoid overflow

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

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

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("Original Array: " + Arrays.toString(arr));

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

        System.out.println("Sorted Array: " + Arrays.toString(arr));
    }
}

---

5. Python Implementation

def merge_sort(arr):
    if len(arr) > 1:
        # Find the middle of the array
        mid = len(arr) // 2

        # Split the array into two halves
        left_half = arr[:mid]
        right_half = arr[mid:]

        # Recursively sort both halves
        merge_sort(left_half)
        merge_sort(right_half)

        # Merge sorted halves
        i = j = k = 0

        # Copy data to original array from left_half and right_half
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        # Check for any remaining elements
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

# Example usage
if __name__ == "__main__":
    arr = [38, 27, 43, 3, 9, 82, 10]
    print("Original Array:", arr)

    merge_sort(arr)

    print("Sorted Array:", arr)

---

6. Optimizations

• Iterative Merge Sort: Replace recursion with iteration to reduce the overhead of recursive calls.
• In-place Merge: Minimize additional memory usage by implementing an in-place merge (complex to implement).

---

7. Advantages and Disadvantages

Advantages:

• Stable Sort: Maintains the relative order of equal elements.
• Guaranteed Performance: Consistently performs O(n log ⁡n) in all cases.

Disadvantages:

• Additional Memory: Requires O(n) extra memory for merging.
• Inefficient for Small Data Sets: For small datasets, simpler algorithms like Insertion Sort can be faster.

---

8. Applications

Merge Sort is commonly used when:

• Stable sorting is required.
• Sorting large datasets that don’t fit into memory (External Sorting).