• +91-9142290450

  • Hajipur, Bihar, 844101

☰
❮
❯

Python Merge Sort

← Previous

Merge sort is a reliable and efficient sorting algorithm that follows the divide and conquer strategy. Instead of sorting a large list in one go, it breaks the list into smaller parts, sorts each part and then merges everything back together in sorted order. Because of this balanced approach, merge sort gives stable and predictable performance even for very large datasets.

In this tutorial, you will learn how merge sort works, how the divide and conquer strategy is applied, how merging happens, how to write the full code in Python and where this algorithm is used in real systems. Understanding merge sort helps you build a strong foundation in advanced sorting techniques.

What Is Merge Sort?

Merge sort is a comparison-based sorting algorithm that divides the list into two halves, sorts them individually and merges them. This merging step is what gives merge sort its accuracy and stability. No matter what order the elements are in, merge sort always performs in O(n log n) time.

The core idea:

  • Split the list into two halves

  • Recursively sort the left half

  • Recursively sort the right half

  • Merge both sorted halves

The algorithm keeps dividing until each sublist contains only one element. Since a single element is already sorted, merging them naturally produces a sorted result.

How Merge Sort Works Step by Step

Let’s take a sample list:

[38, 27, 43, 3, 9, 82, 10]

Step 1: Divide the list

Split into two halves:

Left:

[38, 27, 43]

Right:

[3, 9, 82, 10]

Step 2: Recursively split further

Left -> [38, 27, 43] becomes:

[38] and [27, 43]

Then [27, 43] becomes:

[27] and [43]

Right -> [3, 9, 82, 10] becomes:

[3, 9] and [82, 10]

Then split again:

[3] [9] and [82] [10]

Step 3: Start merging sorted lists

Merge [27] and [43] → [27, 43]
Merge [38] with [27, 43] → [27, 38, 43]

Merge [3] and [9] → [3, 9]
Merge [82] and [10] → [10, 82]
Merge [3, 9] and [10, 82] → [3, 9, 10, 82]

Step 4: Final merge

Merge the two halves:

[27, 38, 43] and [3, 9, 10, 82]

Final sorted output:

[3, 9, 10, 27, 38, 43, 82]

Why Use Merge Sort?

Merge sort has several strong advantages:

  • Always gives O(n log n) performance

  • Works efficiently on very large datasets

  • Stable sorting algorithm

  • Performs well on linked lists

  • Predictable behavior regardless of input order

Its consistent performance is why merge sort is used in many systems where reliability matters.

Merge Sort Algorithm in Python

Here is the complete Python code:

def merge_sort(data):
    if len(data) <= 1:
        return data

    mid = len(data) // 2
    left = merge_sort(data[:mid])
    right = merge_sort(data[mid:])

    return merge(left, right)


def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

This version uses recursion and carefully merges sorted halves. Every merge step builds the final sorted list gradually.

Example Usage

numbers = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(numbers))

Output:

[3, 9, 10, 27, 38, 43, 82]

The same process works for any list of numbers, whether sorted, unsorted or random.

Time Complexity of Merge Sort

Merge sort always shows the same performance:

  • Best case: O(n log n)

  • Average case: O(n log n)

  • Worst case: O(n log n)

This predictable behavior is why merge sort is one of the most dependable sorting algorithms.

Space complexity is O(n) because it uses extra memory during merging.

When Merge Sort Works Best

Merge sort is a good choice when:

  • You need stable sorting

  • You are working with linked lists

  • Input data is large

  • You need reliable performance

  • You want a divide and conquer approach

Systems that handle massive datasets often choose merge sort for its consistency.

When Merge Sort Is Not Suitable

Avoid merge sort when:

  • Memory usage must be minimal

  • You want in-place sorting without extra arrays

  • The list is small and simpler algorithms are faster

In small datasets, insertion sort or bubble sort may perform better due to low overhead.

Real-Life Uses of Merge Sort

Merge sort appears in many real-world scenarios:

External sorting

Large files stored on disk are sorted using merge sort since it works well with chunk-based processing.

Databases

Merging sorted records is a common operation in indexing systems.

Parallel processing

Merge sort works smoothly in multi-threaded environments.

Sorting linked lists

Because merge sort avoids random access, it fits linked list structures naturally.

File systems

File managers often rely on merge-like processes to sort metadata.

Step-by-Step Example

List:

[20, 5, 16, 8]

Step 1: Split
Step 2: Split again
Step 3: Start merging

Final sorted list:

[5, 8, 16, 20]

This simple example shows how breaking down into small pieces helps build an accurate sorted output.

Practical Examples

Example 1: Basic list

print(merge_sort([4, 2, 7, 1]))

Example 2: Reverse order list

print(merge_sort([9, 8, 7, 6]))

Example 3: Already sorted list

print(merge_sort([1, 2, 3, 4]))

Example 4: Duplicate values

print(merge_sort([5, 2, 5, 9, 2]))

Example 5: Single element

print(merge_sort([42]))

Example 6: Mixed numbers

print(merge_sort([10, 3, 15, 7, 8]))

Example 7: Sort user IDs

ids = [103, 501, 209, 88, 15]
print(merge_sort(ids))

Example 8: Sort random values

print(merge_sort([12, 99, 53, 1, 5]))

Example 9: Sort ages list

print(merge_sort([25, 19, 32, 18]))

Example 10: Sort transaction amounts

print(merge_sort([1200, 500, 800, 300]))

Summary of the Tutorial

Merge sort works by dividing the list into smaller halves, sorting them individually and merging them in sorted order. You learned how the divide and conquer approach works, how the merging process helps build the final list, why merge sort is consistent in performance and where it is used in real-world applications. Merge sort is a dependable algorithm for handling large datasets with predictable results.

Practice Questions

Q1. Write a Python program to sort the list [5, 1, 6, 2, 4, 3] using merge sort.

Q2. Write a Python program to modify the merge sort function to print the array after each merge step.

Q3. Write a Python program to sort a list of words alphabetically using merge sort.

Q4. Write a Python program to accept a list of numbers from user input and sort it using merge sort.

Q5. Write a Python program to track and count how many times merging occurs during merge sort.

Q6. Write a Python program to sort a very large list (e.g., 1000+ items) using merge sort.

Q7. Write a Python program to sort a list that contains duplicate values using merge sort.

Q8. Write a Python program to convert recursive merge sort into an iterative version.

Q9. Write a Python program to sort a list in descending order using merge sort.

Q10. Write a Python program to measure and print the time taken to sort a list using merge sort.

← Previous

Try a Short Quiz.

coding learning websites codepractice

No quizzes available.

Python

online coding class codepractice

Introduction to Python

Python Basics

Cotrol Structures

Data Structures

Date and Time

Functions and Module

File Handling

Python OOP

Advanced Concepts

Python DSA

Searching Algorithms

Sorting Algorithms

codepractice logo
Login
Go Back Top