Merge Sort in Python: Step-by-Step Guide with Code Examples

If you're diving into the world of algorithms, chances are you've come across the term merge sort in Python more than once. And there's a good reason for it, as merge sort in Python is not only efficient but also a great example to understand the divide-and-conquer technique. Whether you're preparing for coding interviews or just brushing up on your algorithm skills, learning merge sort in Python will give you a strong foundation.

In many software engineering & development courses, merge sort in Python is introduced as a core concept due to its predictable time complexity and structured approach. This blog walks you through how merge sort in Python works, its implementation with code examples, complexity analysis, and optimization techniques. We'll keep it simple, practical, and packed with insights so you can confidently use merge sort in Python in your own projects.

How Does Merge Sort in Python Work?

Before jumping into code, it’s important to understand the concept behind merge sort in Python. Merge sort is a divide-and-conquer algorithm that breaks a list into smaller sublists until each sublist contains a single element. It then merges those sublists back together in a sorted manner.

Unlock a career at Big Four with the following full-stack development courses: 

• AI-Powered Full Stack Development Course by IIITB 
• Professional Certificate Program in Cloud Computing and DevOps 
• Master of Design in User Experience  

The process of merge sort in Python follows three basic steps:

1. Divide: Split the array into halves recursively until individual elements are left.
2. Conquer: Sort each of those small arrays (which are already sorted as single elements).
3. Combine: Merge the sorted arrays to produce new sorted arrays until you have a fully sorted list.

This recursive strategy makes merge sort in Python especially effective for sorting large datasets with consistent performance. Unlike bubble sort or insertion sort, merge sort in Python doesn’t degrade in performance significantly with unsorted data, making it a preferred method in performance-sensitive scenarios.

Read the OpenCV in Python article to enhance your coding productivity.

Let’s visualize it with a high-level breakdown:

• Start with the unsorted list: `[8, 3, 5, 4, 7, 6, 1, 2]`
• Divide it: `[8, 3, 5, 4]` and `[7, 6, 1, 2]`
• Further divide: `[8, 3]`, `[5, 4]`, `[7, 6]`, `[1, 2]`
• Continue dividing until individual elements: `[8]`, `[3]`, etc.
• Start merging while sorting: `[3, 8]`, `[4, 5]`, `[6, 7]`, `[1, 2]`
• Merge sorted pairs: `[3, 4, 5, 8]` and `[1, 2, 6, 7]`
• Final merge gives: `[1, 2, 3, 4, 5, 6, 7, 8]`

Understanding this flow is crucial before implementing merge sort in Python, as it provides the conceptual clarity needed to write clean, effective code.

Must explore the Operators in Python article to build scalable web applications.

Implementation of Merge Sort in Python

Now that you understand how it works, let’s implement merge sort in Python with clean and well-structured code. This section includes two practical examples: one that sorts a simple list of integers, and another that demonstrates how merge sort in Python can sort a list of custom objects based on a specified attribute.

The recursive approach you’ll see here is a classic form of merge sort in Python, taught widely in computer science programs and software development courses due to its reliability and logical structure.

Go through the Memory Management in Python article to speed up development time.

Example 1: Sorting an Unsorted List of Integers

This first example demonstrates a basic use case of merge sort in Python sorting an unsorted list of integers. It uses the standard recursive merge sort logic.

Code:

# Merge Sort in Python for a list of integers

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

    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])

    return merge(left_half, right_half)

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

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

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

# Example usage
unsorted_list = [38, 27, 43, 3, 9, 82, 10]
sorted_list = merge_sort(unsorted_list)
print("Sorted List (Example 1):", sorted_list)

Output:

Sorted List (Example 1): [3, 9, 10, 27, 38, 43, 82]

Explanation:

This example of merge sort in Python demonstrates how the algorithm recursively breaks down and then merges sublists. The result is a consistently sorted list, regardless of initial disorder.

Refer to the Inheritance in Python article to efficiently implement an important OOPS concept.

Example 2: Sorting a List of Custom Objects

Merge sort in Python can also be applied to more complex data types, such as custom objects. In this example, we'll sort a list of `Employee` objects based on their `age`.

Read Comments in Python to write cleaner, modular code.

Code:

# Merge Sort in Python for custom objects using a key

class Employee:
    def __init__(self, name, age):
        self.name = name
        self.age = age

    def __repr__(self):
        return f"{self.name} ({self.age})"

def merge_sort_objects(arr, key=lambda x: x):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left_half = merge_sort_objects(arr[:mid], key)
    right_half = merge_sort_objects(arr[mid:], key)

    return merge_objects(left_half, right_half, key)

def merge_objects(left, right, key):
    sorted_list = []
    i = j = 0

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

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

# Example usage
employees = [
    Employee("Rajat", 34),
    Employee("Ajay", 25),
    Employee("Anmol", 40),
    Employee("Rahul", 29)
]

# Sort by age using merge sort in Python
sorted_employees = merge_sort_objects(employees, key=lambda emp: emp.age)
print("Sorted List (Example 2):", sorted_employees)

Output:

Sorted List (Example 2): [Ajay (25), Rahul (29), Rajat (34), Anmol (40)]

Explanation:

This example showcases how merge sort in Python can be customized using a `key` parameter similar to how Python’s built-in `sorted()` function works. By passing a lambda function that extracts the `age` attribute, we control how the list of objects is sorted. This flexibility is one reason merge sort in Python is so powerful and frequently taught in software development courses.

Also explore the String Split in Python article to develop efficient Python projects.

These two examples demonstrate how versatile and adaptable merge sort in Python can be capable of sorting both primitive data types and complex objects with equal reliability and precision.

Complexity of Merge Sort in Python

Understanding the efficiency of merge sort in Python is crucial for appreciating why it’s widely used in software development. Let’s analyze its time and space complexity.

Time Complexity

• Best Case: O(n log n)
• Average Case: O(n log n)
• Worst Case: O(n log n)

Regardless of the initial arrangement of data, merge sort in Python consistently performs at O(n log n). This predictability comes from its divide-and-conquer strategy where the list is repeatedly split into halves (log n splits), and each level involves merging all n elements.

Refer to the Python Frameworks article to master modern web frameworks.

Space Complexity

• O(n) additional space is required for temporary arrays during the merge process.
• This makes merge sort in Python not an in-place sorting algorithm, unlike quicksort, but it trades extra space for stable and consistent sorting time.

Why is this important?

Knowing the complexity helps developers decide when to use merge sort in Python. For example, in scenarios where stability and predictable performance are critical like sorting linked lists or large datasets, merge sort in Python is an excellent choice.

Read the Queue in Python article to create powerful backend services.

Optimization of Merge Sort in Python 

While  merge sort in Python  is already efficient, there are several ways to optimize its implementation and improve performance, especially when dealing with large datasets.

1.  Switch to Insertion Sort for Small Sublists 

For very small lists (usually less than 20 elements), insertion sort can be faster than recursive merge sort due to lower overhead. You can modify  merge sort in Python  to switch to insertion sort when sublists become sufficiently small.

2.  Avoid Repeated List Slicing 

Python’s list slicing creates new lists, which adds overhead. Instead of slicing, use indices to track sublists boundaries within the original list. This reduces memory usage and speeds up the algorithm.

Must explore the Reverse String in Python article to understand core string concept.

3.  Use In-Place Merge Sort Variants 

Though the classic  merge sort in Python  uses O(n) extra space, some advanced algorithms perform in-place merging to save memory. These are more complex but useful when memory is limited.

4.  Parallelize the Merge Sort 

Because  merge sort in Python  splits data recursively, the sorting of left and right halves can be done in parallel using Python’s multiprocessing or concurrent futures modules. This takes advantage of multi-core processors for faster sorting.

Conclusion

In this blog, we explored merge sort in Python, a reliable, efficient sorting algorithm based on the divide-and-conquer approach. We walked through how it works, implemented it with clear, commented code, and even saw how it can sort both simple lists and complex custom objects.

We also discussed the time and space complexity of merge sort in Python, highlighting its consistent O(n log n) performance, and covered several optimization techniques to enhance its practical use.

Whether you are a student learning algorithms in software development courses or a developer seeking stable and predictable sorting, mastering merge sort in Python is a valuable skill that applies to many real-world programming challenges.

FAQs

1. What is merge sort in Python?

Merge sort in Python is a sorting algorithm that uses a divide-and-conquer strategy to sort lists. It recursively splits the list into smaller sublists, sorts them, and then merges the sorted sublists to produce the final sorted list. It is known for its consistent O(n log n) time complexity and stability.

2. How does merge sort in Python differ from other sorting algorithms?

Merge sort in Python differs from algorithms like quicksort or bubble sort because it consistently offers O(n log n) time complexity regardless of input. Unlike quicksort, it is stable and guarantees performance, but it uses more memory due to temporary arrays needed for merging, making it less space-efficient.

3. Is merge sort in Python stable?

Yes, merge sort in Python is a stable sorting algorithm. This means that if two elements have the same key or value, their original order is preserved after sorting. Stability is important when sorting complex data structures where maintaining relative order of equal elements matters.

4. Can merge sort in Python be used to sort custom objects?

Absolutely. Merge sort in Python can sort custom objects by using a key function that extracts the attribute to sort by. This flexibility allows you to sort lists of objects like employees by age, name, or any other comparable property, making it useful for a wide range of applications.

5. What is the time complexity of merge sort in Python?

The time complexity of merge sort in Python is O(n log n) in the best, average, and worst cases. This consistent performance comes from dividing the list into halves (log n splits) and merging n elements at each level, ensuring efficient sorting even for large datasets.

6. What is the space complexity of merge sort in Python?

Merge sort in Python requires O(n) additional space for temporary arrays used during the merge process. It is not an in-place sorting algorithm, meaning it uses extra memory proportional to the size of the list, which is a tradeoff for its stable and predictable performance.

7. How can I optimize merge sort in Python?

You can optimize merge sort in Python by switching to insertion sort for very small sublists to reduce overhead, avoiding unnecessary list slicing by using indices, implementing in-place merge variants to save memory, or parallelizing the sorting of sublists to leverage multi-core processors for faster execution.

8. When should I use merge sort in Python over other sorting algorithms?

Merge sort in Python is ideal when you need guaranteed O(n log n) performance and stability, especially for large datasets or when sorting linked lists. It is preferred when stability is important or when predictable sorting times are required, even though it uses more memory than some in-place algorithms.

9. Does merge sort in Python work well with large datasets?

Yes, merge sort in Python handles large datasets efficiently due to its O(n log n) time complexity and predictable performance. However, its additional memory usage may be a consideration in memory-constrained environments. Optimizations and parallel processing can improve its efficiency for very large data.

10. Is merge sort in Python recursive or iterative?

The classic implementation of merge sort in Python is recursive, breaking down the list into smaller sublists until base cases are reached, then merging back sorted lists. However, iterative versions also exist, using bottom-up approaches without recursion to achieve similar results.

11. Can merge sort in Python be implemented in-place?

Traditional merge sort in Python is not in-place as it requires extra space for merging sublists. However, there are advanced in-place merge sort algorithms, though they are more complex to implement and less common. Standard merge sort favors simplicity and stability over minimal memory use.

Take our Free Quiz on Python

Answer quick questions and assess your Python knowledge

Start Quiz