Merge Sort

There is a key note to be made about the implementation of merge sort: it is ideal if we write the function to change the array in place.

The merge sort function itself will not return an array (instead it will modify the input array in place) but the merge procedure will create a copy of the two halves of the array to merge them.

Here is a canonical implementation:

def mergeSort(array):
    if len(array) > 1:
        mid = len(array) // 2
        L = array[:mid]
        M = array[mid:]

        mergeSort(L)
        mergeSort(M)

        i = 0
        j = 0
        k = 0

        while i < len(L) and j < len(M):
            if L[i] < M[j]:
                array[k] = L[i]
                i += 1
            else:
                array[k] = M[j]
                j += 1
            k += 1

        while i < len(L):
            array[k] = L[i]
            i += 1
            k += 1

        while j < len(M):
            array[k] = M[j]
            j += 1
            k += 1

if __name__ == '__main__':
    array = [6, 5, 12, 10, 9, 1]
    mergeSort(array)
    print("Sorted array is: ", end="")
    for i in range(len(array)):
        print(array[i], end=" ")
    print()

Time Complexity

Merge sort is an algorithm where a bulk of the work is done in the conquer (merge) step, leading to the recurrence:

Space Complexity

The auxiliary space complexity will be \(O(n)\).

Example Problems

• Linked List Sorting: Merge sort is preferred for linked lists because it can efficiently sort them with \(O(n \log n)\) time without requiring random access, which other algorithms like QuickSort lack.

  Ideal for linked lists because it doesn't require random access and can be implemented with \(O(n \log n)\) stack space).

  

  

  

• External Sorting: When datasets are too large to fit in RAM (e.g., large file sorting on hard drives), merge sort is used to sort chunks of data, which are then merged.
• Parallel Computing: Merge sort is highly parallelizable, allowing subarrays to be sorted independently in parallel, making it suitable for distributed systems.
• Stability Requirements: In applications where the relative order of equal elements must be maintained (stability), merge sort is favored over quicksort.
• Inversion Counting: It is specifically used to solve problems involving counting inversions, "Count Smaller on Right" problems, and finding the union/intersection of sorted arrays.

  The key ideas is that if an element from the right subarray is smaller than an element from the left subarray, it forms an inversion with all remaining elements in the left subarray.

• Inverted File Indices: It is used in building data structures for search engines, helping to quickly return documents containing specific keywords.