Python Program to Implement Merge Sort

Merge Sort in Python is a recursive sorting algorithm that divides the input list into smaller halves, sorts them separately, and then merges them back together to produce a sorted list.

Write a Python program that sorts a list by using merge sort.

def merge_sort(arr, start, end):
    if start >= end:
        return
 
    mid = (start + end) // 2
    merge_sort(arr, start, mid)
    merge_sort(arr, mid + 1, end)
    merge(arr, start, end, mid)

The merge_sort function takes an array, a start index, and an end index as input. It checks if the start index is greater than or equal to the end index, and if so, it returns. Otherwise, it calculates the middle index and recursively calls merge_sort on the left and right halves of the array. Finally, it merges the divided halves using the merge function.

Here’s a step-by-step example of how the Merge Sort algorithm would sort the list “3 1 5 8 2 5 1 3”:

• Initial list: [3, 1, 5, 8, 2, 5, 1, 3]
• Split the list into halves: [3, 1, 5, 8] and [2, 5, 1, 3]
• Recursively split the left half: [3, 1] and [5, 8]
• Recursively split the right half: [2, 5] and [1, 3]
• Merge the divided halves of the right side: [1, 2, 3, 5]
• Merge the divided halves of the left side: [1, 3, 5, 8]
• Merge the sorted halves of the left and right sides: [1, 1, 2, 3, 5, 5, 8]
• The final sorted list: [1, 1, 2, 3, 5, 5, 8]

The Merge Sort algorithm repeatedly divides the list into smaller halves, sorts them individually, and then merges them back together in a sorted manner. This process continues until the entire list is sorted.

Here is the source code of a Python program to implement merge sort. The program output is shown below.

def merge_sort(alist, start, end):
    '''Sorts the list from indexes start to end - 1 inclusive.'''
    if end - start > 1:
        mid = (start + end)//2
        merge_sort(alist, start, mid)
        merge_sort(alist, mid, end)
        merge_list(alist, start, mid, end)
 
def merge_list(alist, start, mid, end):
    left = alist[start:mid]
    right = alist[mid:end]
    k = start
    i = 0
    j = 0
    while (start + i < mid and mid + j < end):
        if (left[i] <= right[j]):
            alist[k] = left[i]
            i = i + 1
        else:
            alist[k] = right[j]
            j = j + 1
        k = k + 1
    if start + i < mid:
        while k < end:
            alist[k] = left[i]
            i = i + 1
            k = k + 1
    else:
        while k < end:
            alist[k] = right[j]
            j = j + 1
            k = k + 1
 
 
alist = input('Enter the list of numbers: ').split()
alist = [int(x) for x in alist]
merge_sort(alist, 0, len(alist))
print('Sorted list: ', end='')
print(alist)

1. Create a function merge_sort that takes a list and two variables start and end as arguments.
2. The function merge_sort will sort the list from indexes start to end – 1 inclusive.
3. If end – start is not greater than 1, then return.
4. Otherwise, set mid equal to the floor of (start + end)/2.
5. Call merge_sort with the same list and with start = start and end = mid as arguments.
6. Call merge_sort with the same list and with start = mid and end = end as arguments.
7. Call the function merge_list, passing the list and the variables start, mid and end as arguments.
8. The function merge_list takes a list and three numbers, start, mid and end as arguments and assuming the list is sorted from indexes start to mid – 1 and from mid to end – 1, merges them to create a new sorted list from indexes start to end – 1.
9. The sorted list is displayed.

Time complexity: O(n log n)
The Merge Sort algorithm has a time complexity of O(n log n) in all cases, where n is the number of elements in the list. This means the algorithm scales efficiently even for large input sizes.

Space Complexity: O(n)
The Merge Sort algorithm has a space complexity of O(n) in all cases. It requires additional memory to store temporary arrays during the merging process, with the size proportional to the input size.

Testcase 1: Here, the elements are entered in random order.

 
Enter the list of numbers: 3 1 5 8 2 5 1 3
Sorted list: [1, 1, 2, 3, 3, 5, 5, 8]

Testcase 2: Here, the elements are entered in reverse order.

Enter the list of numbers: 5 3 2 1 0
Sorted list: [0, 1, 2, 3, 5]

To practice programs on every topic in Python, please visit “Programming Examples in Python”.