Understanding Merge Sort in Python

Understanding Merge Sort in Python. Merge Sort is a highly efficient, stable, and comparison-based sorting algorithm. It is based on the divide-and-conquer strategy, where the list is divided into two halves, each half is sorted, and then the sorted halves are merged. In this article, we will see the concept and implementation of Merge Sort in Python.

Merge Sort

Before we dive into the code, Let’s understand how Merge Sort works:

• Divide: Split the list into two halves until each sublist contains a single element.
• Conquer: Sort each half recursively.
• Combine: Merge the sorted halves into a single sorted list.

Merge Sort has a best, average, and worst-case time complexity of O(n long n), making it highly efficient for large data sets.

Implementing Merge Sort in Python

Let’s implement Merge Sort in Python step by step-

Merging two Sorted List

The core of the Merge Sort algorithm is the merge process. It involves combining two sorted lists into a single sorted list. Here is how you can implement this.

def merge(left,right):
    result = []
    i,j = 0,0
    # Comapre each element of the two lists and add the smaller one to the result
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i = i+1
        else:
            result.append(right[j])
            j = j+1
    # add the reamining elements of left (if any)
    result.extend(left[i:])
    # add the reamining elements of right (if any) 
    result.extend(right[j:])
    return result

Merge Sort Function

Now that we have the merge function, we can implement the Merge Sort algorithm.

def merge_sort(array):
    # Base case: A list with 0 or 1 element is already sorted
    if len(array)<=1:
        return array
    # Divide the list two halves
    mid = len(array)//2
    left = array[:mid]
    right = array[mid:]
    # Recursively sort each half
    left_sorted = merge_sort(left)
    right_sorted = merge_sort(right)
    # Merge the sorted halves and return
    return merge(left_sorted,right_sorted)

Testing the Merge Sort Algorithm

Now, let’s test our Merge Sort function with a simple list.

unsorted_list = [9,4,6,2,1,7,44,32,100]
sorted_list = merge_sort(unsorted_list)
print(sorted_list)

Merge Sort is a powerful algorithm that uses the divide-and-conquer approach to sort lists efficiently. By understanding its process and implementation in Python, You can tackle sorting problems with greater efficiency. Remember that the key to master merge sort is to understand how the merge process works and how recursive calls facilitate the sorting of smaller arrays.

Happy Coding & Learning

See Also

• Binary Search in Python
• Fibonacci Series in Python