Merge Sort: A Divide and Conquer Algorithm

Sorting is a fundamental operation in computer science and is widely used in various applications. Among the many sorting algorithms, Merge Sort is highly regarded for its efficiency and simplicity. In this blog post, we will delve into the inner workings of Merge Sort, understand its key principles, and explore its time and space complexities.

Table of Contents

• What is Merge Sort?
• How does Merge Sort work?
• Pseudocode for Merge Sort:
• Time and Space Complexity
• Advantages of Merge Sort
• Code in Python
• Conclusion

What is Merge Sort?

Merge Sort is a comparison-based sorting algorithm that follows the divide and conquer strategy. It works by recursively dividing the input array into smaller subarrays, sorting them independently, and then merging the sorted subarrays to produce a sorted output.

How does Merge Sort work?

• Divide: The input array is repeatedly divided into two halves until each subarray contains only one element. This process is accomplished through recursion, which divides the array in a top-down manner.
• Conquer: Once the array is divided into individual elements, the conquer phase begins. In this phase, the adjacent elements are compared and merged in a sorted order. This merging process continues until all subarrays are sorted and merged into a single sorted array.
• Merge: Merging is the key step in Merge Sort. It involves comparing elements from the two sorted subarrays and combining them into a single sorted subarray. This process is repeated until all the subarrays are merged into a single sorted array.

Pseudocode for Merge Sort:

mergeSort(arr):
    if length of arr <= 1:
        return arr
    mid = length of arr / 2
    left = mergeSort(arr[0:mid])
    right = mergeSort(arr[mid:])
    return merge(left, right)

merge(left, right):
    merged = []
    while left is not empty and right is not empty:
        if left[0] <= right[0]:
            append left[0] to merged
            remove first element from left
        else:
            append right[0] to merged
            remove first element from right
    append remaining elements of left to merged
    append remaining elements of right to merged
    return merged

Time and Space Complexity

Merge Sort has a time complexity of O(n log n) in the worst, best, and average cases. This efficiency is due to its divide and conquer approach, as the array is halved in each recursive call.

The space complexity of Merge Sort is O(n) since it requires additional space to store the temporary subarrays during the merging phase. However, it can be optimized to use O(1) additional space by performing the merging in-place.

Advantages of Merge Sort

1. Stability: Merge Sort maintains the relative order of elements with equal values, making it a stable sorting algorithm. This characteristic is crucial when sorting objects with multiple attributes.
2. Efficiency: Merge Sort guarantees a worst-case time complexity of O(n log n), making it efficient for large datasets. It outperforms algorithms like Bubble Sort and Insertion Sort, especially for large arrays.
3. Scalability: Merge Sort’s divide and conquer strategy allows it to be parallelized easily, making it suitable for parallel computing environments. It can take advantage of multi-core processors to further improve its performance.

Code in Python

def merge_sort(values: list) -> list:
    def merge(left: list, right: list) -> list:
        def _merge():
            while left and right:
                yield (left if left[0] <= right[0] else right).pop(0)
            yield from left
            yield from right

        return list(_merge())

    if len(values) <= 1:
        return values
    mid = len(values) // 2
    return merge(merge_sort(values[:mid]), merge_sort(values[mid:]))


if __name__ == "__main__":
    user_input = input("Enter numbers separated by a comma:\n")
    unsorted = [int(item) for item in user_input.split(",")]
    sorted = merge_sort(unsorted)
    for i in sorted:
        print(i,end=',')

Conclusion

Merge Sort is an efficient, stable, and widely used sorting algorithm. By dividing the array into smaller subarrays, sorting them independently, and merging them, Merge Sort achieves an overall sorted array. Its simplicity, combined with a guaranteed worst-case time complexity of O(n log n), makes it a popular choice for various sorting applications. Understanding the inner workings of Merge Sort is valuable knowledge for any programmer or computer science enthusiast.