What is Merge Sort?

Merge Sort is a widely used, efficient, and general-purpose comparison-based sorting algorithm. It belongs to the family of divide-and-conquer algorithms. It is known for its guaranteed O(n log n) time complexity, regardless of the input data's initial order.

Divide and Conquer Approach

Merge Sort follows the divide-and-conquer paradigm. This paradigm involves breaking down a problem into smaller subproblems, solving those subproblems recursively, and then combining the solutions to solve the original problem. In the context of Merge Sort, the divide-and-conquer strategy is applied as follows:

1. Divide: The unsorted list is divided into n sublists, each containing one element (a list of one element is considered sorted).
2. Conquer: Recursively sort each sublist. Since each sublist is already of size 1 (and therefore considered sorted), the "conquer" step effectively does nothing beyond initiating the recursion. The recursion base case is when the sublist size is 1.
3. Combine: Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list. The merging operation takes two sorted sublists and combines them into a new, larger sorted sublist.

Merging Procedure

The core of Merge Sort lies in the merging procedure. This procedure takes two sorted sublists as input and produces a single, sorted list containing all the elements from both sublists. Here's a detailed explanation of the merging process:

1. Initialization:
   • Create two pointers, i and j, initialized to the beginning of the two sorted sublists, left and right, respectively.
   • Create an empty list, result, to store the merged, sorted elements.
2. Comparison and Merging:
   • While both i and j are within the bounds of their respective sublists:
     • Compare the elements at left[i] and right[j].
     • If left[i] is less than or equal to right[j], append left[i] to the result list and increment i.
     • Otherwise, append right[j] to the result list and increment j.
3. Copying Remaining Elements:
   • After one of the sublists is exhausted, copy the remaining elements from the other sublist into the result list. This is done because one of the sublists might have elements left that haven't been processed.
   • If there are any remaining elements in left (i.e., i is less than the length of left), append the remaining elements from left to result.
   • If there are any remaining elements in right (i.e., j is less than the length of right), append the remaining elements from right to result.
4. Return: Return the result list, which now contains the merged and sorted elements from the two input sublists.

Implementation Details

Here's a Python implementation of Merge Sort:

 def merge_sort(arr):
    """Sorts a list using the Merge Sort algorithm."""
    if len(arr) <= 1:
        return arr  # Base case: Already sorted

    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    left = merge_sort(left)  # Recursive call on the left half
    right = merge_sort(right) # Recursive call on the right half

    return merge(left, right)


def merge(left, right):
    """Merges two sorted lists into a single sorted list."""
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    # Append any remaining elements from left and right
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# Example Usage
my_list = [38, 27, 43, 3, 9, 82, 10]
sorted_list = merge_sort(my_list)
print(f"Unsorted List: {my_list}")
print(f"Sorted List: {sorted_list}") 

Explanation of the Code:

• merge_sort(arr) function:
  • Takes an array arr as input.
  • Base Case: If the length of the array is less than or equal to 1, it's already sorted, so it's returned directly.
  • Divide: The array is divided into two halves, left and right, using integer division (//) to find the midpoint.
  • Conquer: The merge_sort function is called recursively on both left and right halves.
  • Combine: The merge function is called to merge the sorted left and right halves into a single sorted array. The merged result is then returned.
• merge(left, right) function:
  • Takes two sorted arrays, left and right, as input.
  • Initializes an empty list result to store the merged elements, and two index pointers i and j to point to the beginning of the left and right arrays, respectively.
  • Compares elements at left[i] and right[j]. The smaller element is appended to the result list, and the corresponding index pointer is incremented. This process continues until one of the arrays is exhausted.
  • After one of the arrays is exhausted, the remaining elements from the other array are appended to the result list using the extend method.
  • The merged and sorted result list is returned.

Time Complexity Analysis

Merge Sort boasts a consistent O(n log n) time complexity for all cases (best, average, and worst). This makes it a highly predictable and reliable sorting algorithm.

• Divide Step: Dividing the array takes O(1) time. This is a constant time operation as it only calculates the midpoint. However, this step is performed log₂(n) times because we are repeatedly dividing the array in half.
• Conquer Step: Recursively sorting the sublists takes T(n/2) time for each half, where T(n) represents the time complexity of sorting an array of size n.
• Merge Step: The merge operation takes O(n) time to merge two sorted sublists of size n/2 into a sorted list of size n. Each element needs to be compared and placed into the correct position in the merged list.

Therefore, the recurrence relation for Merge Sort's time complexity can be expressed as:

T(n) = 2T(n/2) + O(n)

This recurrence can be solved using the Master Theorem or by drawing a recursion tree. The solution is O(n log n).

Explanation of O(n log n):

• The log n factor comes from the number of levels of recursion in the divide step. We repeatedly divide the array in half until we reach sublists of size 1. The number of divisions required is proportional to the logarithm (base 2) of the array size.
• The n factor comes from the linear time complexity of the merge operation. At each level of recursion, we merge a total of n elements.

Space Complexity:

Merge Sort is not an in-place sorting algorithm. It requires additional space for the merging process. The space complexity is O(n) because it needs to create temporary arrays to hold the merged sublists.