Concept

Merge Sort is a divide-and-conquer sorting algorithm that recursively divides an array into smaller subarrays, sorts them, and then merges them back into a single sorted array. It is stable (preserves the relative order of equal elements) and widely used due to its predictable performance.

Why Use Merge Sort?

• Purpose: Merge Sort is ideal for sorting large datasets or linked lists due to its O(n log n) time complexity, which is significantly better than the O(n²) of simpler algorithms like Bubble Sort.
• Relevance: It is used in real-world applications like external sorting (sorting data too large to fit in memory), Java’s Arrays.sort() for objects, and Python’s Timsort (which incorporates Merge Sort for larger subarrays).
• Limitations: Requires O(n) extra space for the temporary array during merging, making it less memory-efficient than in-place algorithms like Selection Sort.

Key Characteristics

• Divide: Split the array into two halves (hypothetically, using indices).
• Conquer: Recursively sort each half.
• Merge: Combine the sorted halves into a single sorted array.

Time and Space Complexity

• Time Complexity:
  • Best Case: O(n log n) (array is already sorted)
  • Average Case: O(n log n)
  • Worst Case: O(n log n) (array is reverse sorted)
• Space Complexity: O(n) (due to the temporary array used in merging)

Divide-and-Conquer Strategy

How It Works

1. Divide: Split the array into two roughly equal parts by finding the middle index (mid = (low + high) / 2).
2. Recurse: Recursively apply Merge Sort to the left half (low to mid) and the right half (mid + 1 to high).
3. Base Case: Stop dividing when a subarray has one element (already sorted).
4. Merge: Merge the sorted subarrays into a single sorted array by comparing elements and placing them in a temporary array, then copying back to the original array.