Implementing Merge Sort in Python

Implementing Merge Sort in Python

Sorting algorithms are essential tools in a programmer's toolkit. They allow us to efficiently organize and arrange data in a specific order. One such popular sorting algorithm is Merge Sort. In this tutorial, we will dive into the details of Merge Sort and learn how to implement it in Python.

Understanding Merge Sort

Merge Sort is a divide-and-conquer algorithm that works by repeatedly dividing the input array into smaller subarrays until each subarray consists of only one element. It then merges these subarrays in a sorted manner until the entire array is sorted.

The algorithm follows these steps:

1. Divide the unsorted array into two halves.
2. Recursively divide each half into smaller subarrays until each subarray contains only one element.
3. Merge the subarrays back together in a sorted order, comparing and merging elements in an ascending or descending fashion.

Let's take a closer look at each step and implement it in Python.

Step 1: Divide the Array

The first step of Merge Sort is to divide the unsorted array into two halves. We can accomplish this by finding the middle index of the array and splitting it into left and right subarrays.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    # ...

Step 2: Recursively Divide

Next, we recursively divide each subarray until we obtain subarrays containing only one element. We achieve this by calling the merge_sort() function on the left and right subarrays.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    
    left = merge_sort(left)
    right = merge_sort(right)
    # ...

Step 3: Merge the Subarrays

Finally, we merge the subarrays back together in a sorted order. To do this, we compare elements from the left and right subarrays and copy them into a new merged array until one of the subarrays is empty. Then, we append the remaining elements of the non-empty subarray to our merged array.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    
    left = merge_sort(left)
    right = merge_sort(right)
    
    merged = []
    while left and right:
        if left[0] < right[0]:
            merged.append(left.pop(0))
        else:
            merged.append(right.pop(0))
    
    # Append remaining elements
    merged.extend(left)
    merged.extend(right)
    
    return merged

Putting It All Together

Now that we have implemented the three steps of Merge Sort, let's test our implementation with a sample array.

arr = [9, 3, 7, 1, 5, 6, 8, 2, 4]
sorted_arr = merge_sort(arr)
print(sorted_arr)

Output:

[1, 2, 3, 4, 5, 6, 7, 8, 9]

Congratulations! You have successfully implemented Merge Sort in Python. This sorting algorithm has a time complexity of O(n log n) and is often preferred for its efficiency.

Conclusion

In this tutorial, we learned about the Merge Sort algorithm and how to implement it in Python. By breaking down the array into smaller subarrays and merging them in a sorted order, we can efficiently sort large sets of data. Incorporate Merge Sort into your projects and take advantage of its superior time complexity for sorting operations.