Merge Sort in Ascending Order in Python

1. Introduction

In this blog post, we will learn how to write a Python program to sort an array of integers in an Ascending Order using the Merge Sort algorithm.

Merge Sort is a comparison-based, divide-and-conquer sorting algorithm. It divides the unsorted list into halves, recursively sorts the two halves, and then merges the sorted halves to produce the sorted list. Here, we'll implement Merge Sort in Python to sort a list in ascending order.

2. Program Overview

1. merge_sort(): The primary function to sort the array using the Merge Sort algorithm.

2. merge(): A utility function that merges two sorted sub-arrays into a single sorted array.

3. A sample list to test the sorting process.

3. Code Program

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # Find the middle of the array
        L = arr[:mid]  # Split the array elements into 2 halves
        R = arr[mid:]

        merge_sort(L)  # Sorting the first half
        merge_sort(R)  # Sorting the second half

        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]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        # Checking if any element was left
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

def print_list(arr):
    for i in arr:
        print(i, end=" ")
    print()

# Driver code to test the functions
if __name__ == "__main__":
    arr = [64, 34, 25, 12, 22, 11, 90]
    print("Original list is:")
    print_list(arr)

    merge_sort(arr)

    print("\nSorted list in ascending order is:")
    print_list(arr)

Output:

Original list is:
64 34 25 12 22 11 90 

Sorted list in ascending order is:
11 12 22 25 34 64 90 

4. Step By Step Explanation

1. merge_sort(): This function divides the list into two halves, recursively sorts them using merge_sort(), and then merges the two sorted halves using the merge() function.

2. merge(): This utility function is integrated within the merge_sort(). It merges two already sorted arrays in such a way that the resultant array is also sorted.

3. print_list(): A helper function to display the list elements.

4. Driver code: It illustrates the functionality using a sample list.

Merge Sort, due to its divide-and-conquer nature, boasts a consistent O(n log n) time complexity for all cases (best, average, and worst). This makes it one of the most efficient sorting algorithms for larger datasets.

Related Python Programs on Sorting Algorithms

1. Bubble Sort in Ascending Order in Python
2. Bubble Sort in Descending Order in Python
3. Selection Sort in Ascending Order in Python
4. Selection Sort in Descending Order in Python
5. Insertion Sort in Descending Order in Python
6. Insertion Sort in Ascending Order in Python
7. Merge Sort in Ascending Order in Python
8. Merge Sort in Descending Order in Python
9. Quick Sort in Ascending Order in Python
10. Quick Sort in Descending Order in Python
11. Heap Sort in Ascending Order in Python
12. Heap Sort in Descending Order in Python