Merge Sort

Merge Sort

Merge Sort is a classic example of a divide-and-conquer algorithm, used for sorting an array or list of elements. It is an efficient, stable, and comparison-based sorting algorithm with a guaranteed time complexity of $O(n \log n)$, making it much more efficient than simpler algorithms like bubble sort or insertion sort, especially for large datasets.

---

How Merge Sort Works

The core idea of merge sort is to divide the array into smaller subarrays, recursively sort these subarrays, and then merge them back together in sorted order. The process follows three main steps:

1. Divide: Split the array into two halves.
2. Conquer: Recursively sort each of the two halves.
3. Combine: Merge the two sorted halves back together to form a single sorted array.

---

Merge Sort Algorithm

1. Divide: The array is split into two halves.
2. Conquer: Each half is sorted recursively.
3. Combine: The sorted halves are merged together.

This recursive breakdown continues until each subarray contains just one element, which is trivially sorted.

Step-by-step Explanation:

1. Divide: The array is recursively divided in half until each subarray contains a single element.
2. Merge: Once the base case (a subarray with a single element) is reached, the algorithm starts merging the subarrays back together. During the merge step, two sorted subarrays are combined into one sorted array.

---

Merge Sort Code Implementation:

Here’s an example implementation of Merge Sort in Python:

def merge_sort(arr):
    # Base case: if the array has one or no elements, it's already sorted
    if len(arr) <= 1:
        return arr
    
    # Divide: Find the middle point and divide the array into two halves
    mid = len(arr) // 2
    left_half = arr[:mid]  # Left half
    right_half = arr[mid:]  # Right half
    
    # Conquer: Recursively sort both halves
    left_sorted = merge_sort(left_half)
    right_sorted = merge_sort(right_half)
    
    # Combine: Merge the sorted halves
    return merge(left_sorted, right_sorted)

def merge(left, right):
    sorted_arr = []
    i = j = 0
    
    # Merge two sorted arrays into one
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_arr.append(left[i])
            i += 1
        else:
            sorted_arr.append(right[j])
            j += 1
    
    # Append any remaining elements from left or right
    sorted_arr.extend(left[i:])
    sorted_arr.extend(right[j:])
    
    return sorted_arr

---

Explanation of the Code:

1. merge_sort(arr):

   • If the array has one or zero elements, it’s already sorted, so the function returns the array as is (base case).
   • The array is split into two halves at the middle (mid), and each half is recursively sorted using the merge_sort function.

2. merge(left, right):

   • This function takes two sorted arrays, left and right, and merges them into one sorted array.
   • It uses two pointers (i and j) to iterate through both arrays, comparing the elements and adding the smaller element to the sorted array.
   • Once one of the arrays is exhausted, the remaining elements of the other array are appended to the result.

---

Time Complexity of Merge Sort

The time complexity of Merge Sort is dominated by the two operations: divide and merge.

1. Divide step: The array is repeatedly divided into halves. Since each division splits the problem in half, the depth of the recursion is $O(\log n)$.
2. Merge step: Merging two sorted subarrays takes linear time, $O(n)$, where $n$ is the number of elements being merged.

Therefore, the overall time complexity is:

$$T(n) = O(n \log n)$$

This is true for both the best, average, and worst cases, making Merge Sort one of the most efficient general-purpose sorting algorithms.

---

Space Complexity

Merge Sort requires extra space for the temporary subarrays during the merge process. Therefore, its space complexity is:

$$O(n)$$

This is because, at each level of recursion, new subarrays are created for merging, and the maximum size of the subarray is $n$ (the size of the input array).

---

Properties of Merge Sort

1. Stable: Merge Sort is a stable sorting algorithm, meaning that if two elements are equal, their relative order remains unchanged after sorting.
2. Non-Comparison Based Sorting: Unlike algorithms like Quick Sort or Heap Sort, which are comparison-based, Merge Sort doesn’t compare individual elements to each other in the same way; it compares subarrays.
3. Efficient for Linked Lists: Merge Sort is particularly efficient when sorting linked lists since it does not require random access to elements (unlike Quick Sort or Heap Sort).
4. External Sorting: Merge Sort is often used in external sorting algorithms where the data doesn’t fit into memory (i.e., stored on disk). This is because it can merge large chunks of data efficiently in external storage.

---

Example of Merge Sort Execution

Consider an array of numbers:

$[38, 27, 43, 3, 9, 82, 10]$

1. First division: The array is split into two halves:

   • Left: [38, 27, 43, 3]
   • Right: [9, 82, 10]

2. Recursively divide each subarray until each subarray has one element:

   • Left: [38, 27, 43, 3] becomes [38, 27] and [43, 3], which further split to [38], [27], [43], and [3].
   • Right: [9, 82, 10] becomes [9], [82], and [10].

3. Merge the subarrays in sorted order:

   • Merging [38] and [27] gives [27, 38].
   • Merging [43] and [3] gives [3, 43].
   • Merging [9] and [82] gives [9, 82].
   • Merging [10] and [82] gives [10, 82].

4. Combine all the merged subarrays:

   • Merging [27, 38] and [3, 43] gives [3, 27, 38, 43].
   • Merging [9, 82] and [10] gives [9, 10, 82].
   • Final merge of [3, 27, 38, 43] and [9, 10, 82] gives the sorted array:

   $[3, 9, 10, 27, 38, 43, 82]$

---

Advantages of Merge Sort:

1. Guaranteed Time Complexity: It always runs in $O(n \log n)$ time, making it a reliable and predictable sorting algorithm.
2. Stable: Since it’s stable, it preserves the relative order of equal elements.
3. Efficient for Large Data: Its $O(n \log n)$ performance is efficient even for large data sets.
4. Useful for Linked Lists: Works well with linked lists and large data sets that do not fit in memory (external sorting).

---

Disadvantages of Merge Sort:

1. Space Complexity: Merge Sort requires $O(n)$ additional space, which is more than comparison-based algorithms like Quick Sort or Heap Sort.
2. Slower than Quick Sort: For smaller datasets, Merge Sort is generally slower than Quick Sort due to the overhead of recursive calls and merging operations.

---

Summary

Merge Sort is an efficient and stable sorting algorithm that works by recursively dividing the array into two halves, sorting each half, and then merging the sorted halves. Its time complexity is $O(n \log n)$ in all cases, and it is especially useful for large datasets or when sorting linked lists. However, its space complexity is $O(n)$, which can be a limitation for very large arrays. Despite this, it is a reliable and often-used sorting algorithm in practice.