Merge Sort in Python – Explanation, Algorithm, and Program

Sorting is one of the most important operations in computer science. It is used to arrange data in a specific order, usually ascending or descending. Many applications such as searching, data analysis, and database management require sorted data.

One of the most efficient and widely used sorting techniques is Merge Sort. It is a divide-and-conquer algorithm that divides a list into smaller parts, sorts them, and then merges them back together.

This article explains merge sort clearly with algorithm, Python program, and output.

 

---

 

What is Merge Sort

Merge sort is a sorting algorithm that works by repeatedly dividing an array into two halves until each part contains a single element. Then these smaller sorted parts are merged step by step to produce a fully sorted array.

It follows the divide and conquer approach:

• Divide the array into two halves

• Sort each half recursively

• Merge the sorted halves

Merge sort guarantees stable and efficient sorting even for large datasets.

 

---

 

Algorithm of Merge Sort

Step 1: Divide the array into two halves
Step 2: Recursively sort the left half
Step 3: Recursively sort the right half
Step 4: Merge the two sorted halves
Step 5: Repeat until array is sorted

 

---

 

 def merge_sort(array):

    """Sorts an array using the merge sort algorithm."""

    if len(array) > 1:

        mid = len(array) // 2

        L = array[:mid]

        M = array[mid:]

        merge_sort(L)

        merge_sort(M)

        i = j = k = 0

        while i < len(L) and j < len(M):

            if L[i] < M[j]:

                array[k] = L[i]

                i += 1

            else:

                array[k] = M[j]

                j += 1

            k += 1

        while i < len(L):

            array[k] = L[i]

            i += 1

            k += 1

        while j < len(M):

            array[k] = M[j]

            j += 1

            k += 1

def print_list(array):

    for i in range(len(array)):

        print(array[i], end=" ")

    print()

if __name__ == '__main__':

    data = [6, 5, 12, 10, 9, 1]

    print("Original array is: ")

    print_list(data)

    merge_sort(data)

    print("Sorted array is: ")

    print_list(data)

 

---

 

Explanation of the Program

The function merge_sort() recursively divides the array into two halves using the middle index. The left half is stored in list L and the right half in list M.

Both halves are sorted by calling the same function again. This recursive process continues until each sub-array contains only one element.

After dividing, the algorithm merges the two sorted halves by comparing elements from both lists and placing the smaller element into the original array. This merging continues until all elements are arranged in sorted order.

The function print_list() is used to display the array elements before and after sorting.

 

---

 

Time Complexity of Merge Sort

Merge sort has consistent performance:

• Best case: O(n log n)

• Average case: O(n log n)

• Worst case: O(n log n)

This makes merge sort efficient for large datasets compared to simple sorting methods like bubble sort or selection sort.

---

Advantages of Merge Sort

• Efficient for large data

• Stable sorting algorithm

• Works well with linked lists

• Predictable performance

• Suitable for external sorting

---

Conclusion

Merge sort is a powerful and efficient sorting algorithm based on the divide-and-conquer technique. It divides the data into smaller parts, sorts them recursively, and merges them into a fully sorted array. Because of its guaranteed O(n log n) performance, merge sort is widely used in real-world applications involving large datasets.

This Python implementation clearly demonstrates how merge sort works step by step.

 

---