Python Merge Sort

Python Merge Sort

Merge Sort is a highly efficient, comparison-based sorting algorithm. It is a classic example of a Divide and Conquer algorithm.

A "Divide and Conquer" strategy involves three steps:

1. Divide: Break the problem into smaller subproblems.
2. Conquer: Solve the subproblems recursively. If they are small enough, solve them directly.
3. Combine: Combine the solutions of the subproblems to get the solution for the original problem.

How Merge Sort Works

1. Divide: The algorithm starts by dividing the unsorted list into n sublists, each containing one element (a list of one element is considered sorted).
2. Conquer & Combine: It then repeatedly merges these sublists to produce new, sorted sublists until there is only one sorted list remaining. The "merge" step is the core of the algorithm. It takes two smaller sorted lists and combines them into a single, sorted new list.

!Merge Sort Diagram

Implementing Merge Sort in Python

The implementation involves a recursive function that splits the list and a helper function that merges two sorted lists.

def merge_sort(data):
    if len(data) > 1:
        # Finding the mid of the array
        mid = len(data) // 2
        # Dividing the array elements into 2 halves
        L = data[:mid]
        R = data[mid:]
        # Sorting the first and second halves
        merge_sort(L)
        merge_sort(R)
        i = j = k = 0
        # Copy data to temp arrays L[] and R[]
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                data[k] = L[i]
                i += 1
            else:
                data[k] = R[j]
                j += 1
            k += 1
        # Checking if any element was left
        while i < len(L):
            data[k] = L[i]
            i += 1
            k += 1
        while j < len(R):
            data[k] = R[j]
            j += 1
            k += 1

--- Usage ---
my_list = [12, 11, 13, 5, 6, 7]
merge_sort(my_list)
print("Sorted list is:", my_list)

Time Complexity

Merge sort has a very predictable and stable performance.

• Best Case: O(n log n)
• Worst Case: O(n log n)
• Average Case: O(n log n)

Its main disadvantage is that it requires extra space to store the merged sublists. The space complexity is O(n), making it an "out-of-place" algorithm.