• +91-9142290450

  • Hajipur, Bihar, 844101

☰
❮
❯

Python Merge Sort

← Previous

Merge Sort is a classic divide-and-conquer algorithm.
It splits the array into halves, recursively sorts each half, and merges the sorted halves back together.

Merge sort is stable and has a guaranteed time complexity of O(n log n).

🔹 How Merge Sort Works

  1. Divide the array into two halves

  2. Recursively sort each half

  3. Merge the two sorted halves into one sorted array

🔹 Merge Sort in Python

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        # Merge the sorted halves
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        # Copy remaining elements
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1
Example
nums = [38, 27, 43, 3, 9, 82, 10]

merge_sort(nums)
print("Sorted array:", nums)

✅ Output:

Sorted array: [3, 9, 10, 27, 38, 43, 82]

🔹 Time and Space Complexity

Case Time
Best Case O(n log n)
Average O(n log n)
Worst Case O(n log n)
Space O(n)

Merge Sort always performs consistently regardless of data order.

🔹 Use Cases of Merge Sort

  • Sorting linked lists

  • Sorting large datasets

  • When stable sort is needed

  • Performance is predictable

🔹 Features of Merge Sort

✅ Stable sort
✅ Recursive algorithm
✅ No worst-case O(n²)
❌ Requires additional memory

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

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