• Hajipur, Bihar, 844101

ā˜°
ā®
āÆ

Python

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

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.

Python Merge Sort Quiz

Q1: What is the main strategy of merge sort?

A. Compare and swap
B. Divide and conquer
C. Hashing
D. Heapifying

Q2: What happens after splitting in merge sort?

A. Reversing
B. Sorting and merging
C. Counting
D. Swapping

Q3: Best-case time complexity of merge sort?

A. O(n)
B. O(log n)
C. O(n log n)
D. O(nĀ²)

Q4: Merge Sort is a __________ sort.

A. Stable
B. Unstable
C. In-place
D. Non-deterministic

Q5: Space complexity of merge sort?

A. O(1)
B. O(n)
C. O(log n)
D. O(nĀ²)

Q6: Can Merge Sort handle negative numbers?

A. Yes
B. No
C. Only if converted to positive
D. Only in descending order

Q7: Which data structure works well with merge sort?

A. Heap
B. HashMap
C. Linked List
D. Tree

Q8: What does the merge step do in Merge Sort?

A. Remove duplicates
B. Join and sort two lists
C. Split the array into halves
D. Swap unsorted elements

Q9: Merge sort is ideal for:

A. Small lists
B. Lists with repeated elements
C. Sorting linked lists
D. Sorting queues

Q10: Can Merge Sort be implemented iteratively?

A. Yes
B. No
C. Only for small arrays
D. Only with recursion
ā† Previous
Login
Go Back Top