Merge Sort Python: Comprehensive Guide

Sorting is a super common programming task, and Merge Sort is a powerful algorithm widely used due to its efficiency, particularly for large datasets.

By the end of this guide, you will have a solid understanding of how to implement a merge sort Python style.

Merge Sort is a comparison-based, divide-and-conquer sorting algorithm with a time complexity of O(n log n), making it more efficient than simpler algorithms like bubble sort or insertion sort, especially when dealing with large datasets. Let’s get into it…

What is Merge Sort?

Merge sort is a divide-and-conquer algorithm that breaks down a list into smaller sublists until each sublist contains a single element. It then merges these sublists in a sorted manner to produce a final sorted list. Merge sort is a stable sorting algorithm, meaning that it maintains the relative order of elements with equal values, which is often desirable in many applications.

Key Characteristics of Merge Sort:

• Stable: Retains the order of equal elements.
• Divide and Conquer: Divides the list into smaller parts, sorts them, and merges them back together.
• Time Complexity: O(n log n), making it efficient for large lists.
• Space Complexity: O(n) because it requires additional memory to hold the sublists during the merging process.

How Merge Sort Works

Step-by-Step Breakdown of the Merge Sort Algorithm:

1. Divide: Split the list into two halves recursively until each sublist contains only one element.
2. Conquer: Recursively sort the sublists.
3. Merge: Combine the sorted sublists into a single sorted list.

Example:

Consider the list [38, 27, 43, 3, 9, 82, 10].

Step 1: Divide the List

We recursively split the list into halves:

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

Step 2: Conquer

We now have sublists with a single element, which are trivially sorted.

Step 3: Merge

We recursively merge the sublists, ensuring that the resulting lists are sorted at each step:

[38] [27] -> [27, 38]
[27, 38] [43] -> [27, 38, 43]

[3] [9] -> [3, 9]
[82] [10] -> [10, 82]
[3, 9] [10, 82] -> [3, 9, 10, 82]

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

The final sorted list is: [3, 9, 10, 27, 38, 43, 82].

Implementing Merge Sort in Python

Now that we understand how the algorithm works, let’s implement merge sort in Python. We’ll write a recursive function that performs the divide, conquer, and merge steps.

Python Code for Merge Sort

def merge_sort(arr):
    # Base case: if the list has one element, return it (already sorted)
    if len(arr) <= 1:
        return arr

    # Divide the list into two halves
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]

    # Recursively sort each half
    left_sorted = merge_sort(left_half)
    right_sorted = merge_sort(right_half)

    # Merge the sorted halves
    return merge(left_sorted, right_sorted)

def merge(left, right):
    merged = []
    left_index, right_index = 0, 0

    # Compare elements from both sublists and merge them in sorted order
    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:
            merged.append(left[left_index])
            left_index += 1
        else:
            merged.append(right[right_index])
            right_index += 1

    # If there are remaining elements in the left or right sublist, append them
    merged.extend(left[left_index:])
    merged.extend(right[right_index:])

    return merged

# Example usage
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("Sorted array:", sorted_arr)

Explanation:

• Base Case: The recursion stops when the list has 1 or 0 elements, as these are already sorted.
• Divide: The list is split into two halves (left_half and right_half).
• Conquer: Each half is recursively sorted using merge_sort().
• Merge: The two sorted halves are merged back together using the merge() function.

Example Output:

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

Detailed Breakdown of the Merge Function

The merge() function plays a crucial role in the merge sort algorithm. Let’s take a closer look at how it works:

Merging Two Sorted Lists:

• We compare the first elements of the two sorted sublists (left and right).
• Append the smaller element to the result list (merged).
• Move the pointer of the sublist from which the element was taken.
• Repeat until all elements from one sublist have been added.
• Finally, add any remaining elements from the other sublist.

Example of Merging:

left = [27, 38, 43]
right = [3, 9, 10, 82]

Step-by-step merge:
- Compare 27 and 3 -> [3]
- Compare 27 and 9 -> [3, 9]
- Compare 27 and 10 -> [3, 9, 10]
- Compare 27 and 82 -> [3, 9, 10, 27]
- Compare 38 and 82 -> [3, 9, 10, 27, 38]
- Compare 43 and 82 -> [3, 9, 10, 27, 38, 43]
- Add remaining element 82 -> [3, 9, 10, 27, 38, 43, 82]

Time Complexity of Merge Sort

Merge sort’s time complexity is O(n log n). This is because:

• The list is recursively divided into halves, which happens in log n steps.
• Each level of recursion involves merging, which takes O(n) time to combine all the elements.

Space Complexity

Merge sort requires O(n) additional space to store the temporary lists created during the merging process. This makes it less space-efficient compared to in-place sorting algorithms like quicksort or heapsort.

Advantages of Merge Sort

1. Stable Sorting: Merge sort maintains the relative order of equal elements, making it stable.
2. O(n log n) Time Complexity: Merge sort guarantees O(n log n) performance for all input sizes, making it efficient for large datasets.
3. Consistent Performance: Merge sort performs consistently well even in the worst-case scenario, unlike quicksort which can degrade to O(n²) in some cases.

Disadvantages of Merge Sort

1. Memory Usage: Merge sort requires O(n) additional memory, as it uses temporary arrays for merging. This can be a disadvantage for memory-constrained systems.
2. Not In-Place: Merge sort is not an in-place sorting algorithm because it requires additional storage space for merging the sublists.

Best Practices for Using Merge Sort in Python

1. Use Merge Sort for Large Datasets: Merge sort’s O(n log n) time complexity makes it a good choice for sorting large datasets where performance consistency is important.
2. Avoid Merge Sort for Memory-Constrained Environments: Since merge sort requires additional memory for merging, it might not be the best choice for systems with limited memory.
3. Choose Merge Sort for Linked Lists: Merge sort works efficiently with linked lists because merging does not require shifting elements, which is costly in a linked list. The performance benefit in this case can be significant.
4. Use Python’s Built-in Sorting for Small Lists: Python’s built-in sorted() function uses Timsort, a hybrid algorithm that combines merge sort and insertion sort, making it highly optimized for most cases.

Summary of Key Concepts

• Merge sort is a divide-and-conquer algorithm that splits a list into smaller sublists, sorts them, and merges them back together.
• The time complexity of merge sort is O(n log n), making it highly efficient for large datasets.
• Merge sort is a stable sorting algorithm that preserves the relative order of equal elements.
• The merge sort algorithm is not in-place and requires O(n) additional space.
• Merge sort performs consistently well even in the worst case, unlike quicksort, which can degrade in performance with certain input.

Exercises

1. Merge Sort Implementation: Implement the merge sort algorithm from scratch and test it on an unsorted list of integers.
2. Merge Two Sorted Lists: Write a Python function that merges two pre-sorted lists into one sorted list without using the built-in sorted() function.
3. Measure Merge Sort Performance: Compare the performance of your merge sort implementation with Python’s built-in sorted() function on large datasets.
4. Merge Sort with Linked Lists: Modify the merge sort algorithm to sort a linked list and measure its performance.

Check out our FREE Learn Python Programming Masterclass to hone your skills or learn from scratch.

The course covers everything from first principles to Graphical User Interfaces and Machine Learning

FAQ

Q1: How is merge sort different from quicksort?

A1: Merge sort and quicksort are both divide-and-conquer algorithms, but they differ in their approach:

• Merge Sort splits the list into halves and recursively sorts them, then merges the sorted halves back together. It has a time complexity of O(n log n) in all cases (best, average, and worst).
• Quicksort chooses a pivot element and partitions the list around the pivot, recursively sorting the partitions. While quicksort’s average case time complexity is O(n log n), its worst-case time complexity is O(n²), though this is rare with good pivot selection.
• Merge Sort is a stable sort and not in-place, meaning it requires extra memory, whereas quicksort is typically in-place but not stable.

Q2: Why does merge sort have a space complexity of O(n)?

A2: Merge sort requires additional space to store the temporary sublists during the merging process. When the list is divided, two temporary arrays are created to hold the left and right halves. After the recursive sorting, these arrays are merged into a new list. This extra memory usage leads to the O(n) space complexity.

Q3: Can merge sort be implemented in-place to avoid extra memory usage?

A3: Merge sort is generally not implemented in-place because the merging process requires additional memory to store the two halves. However, it is possible to implement an in-place merge sort, though it becomes much more complex and less efficient compared to the standard version. In most cases, it’s not worth the complexity when compared to other in-place algorithms like quicksort.

Q4: When should I use merge sort over Python’s built-in sorted() function?

A4: You generally don’t need to use merge sort manually for typical sorting tasks in Python, as Python’s sorted() function is optimized and uses Timsort, which combines merge sort and insertion sort for improved performance. However, you may want to use merge sort if:

• You’re dealing with a linked list, as merge sort works more efficiently with linked lists compared to array-based sorting algorithms.
• You need a stable sort and you’re implementing sorting from scratch.
• You’re working in an environment where the merge sort’s consistent O(n log n) time complexity is preferable over quicksort’s worst-case O(n²) time complexity.

Q5: Is merge sort always better than bubble sort or selection sort?

A5: Yes, merge sort is almost always better than bubble sort or selection sort for larger datasets because:

• Merge sort has a time complexity of O(n log n), while both bubble sort and selection sort have O(n²) time complexity.
• For large lists, bubble sort and selection sort will be much slower than merge sort, especially as the size of the dataset increases.
• Merge sort is more efficient for handling large datasets and guarantees faster performance in almost all scenarios.

Q6: How does merge sort handle duplicate elements? Is it stable?

A6: Yes, merge sort is a stable sorting algorithm. This means that it maintains the relative order of duplicate elements in the list. If two elements are equal, their order will remain the same after sorting, which can be important when sorting objects or records by multiple criteria.

Q7: Why does merge sort work well with linked lists?

A7: Merge sort is particularly efficient with linked lists because:

• Splitting a linked list in half and merging sorted halves doesn’t require shifting elements, which can be costly with linked lists.
• Linked lists do not have random access like arrays, so operations like insertion or merging can be more efficient in a linked list.
• The need for extra memory to store temporary arrays is minimized since linked lists are easier to manipulate in terms of pointers, making merge sort a natural fit for linked list sorting.

Q8: Can I implement merge sort iteratively instead of recursively?

A8: Yes, it is possible to implement merge sort iteratively, but it is typically more complex and less intuitive than the recursive version. An iterative version of merge sort would involve dividing the list into smaller sublists and then iteratively merging them in a bottom-up manner. While this avoids recursion depth issues, the recursive approach is generally simpler to understand and implement.

Q9: What are the best use cases for merge sort?

A9: Merge sort is particularly useful in the following scenarios:

• Large datasets where consistent O(n log n) performance is required.
• Situations where stability is important, such as sorting objects by one attribute while maintaining the order of another.
• Linked lists, where merge sort’s non-reliance on index-based access makes it more efficient than other sorting algorithms.
• Applications where you expect data to be in a worst-case scenario for quicksort, as merge sort’s performance does not degrade with input characteristics.

Q10: Is merge sort suitable for sorting very small lists?

A10: While merge sort is efficient for larger datasets, for very small lists (typically fewer than 10 elements), simpler algorithms like insertion sort or even Python’s sorted() function (which uses Timsort) may be more efficient. The overhead of recursion and merging can outweigh the benefits of merge sort for small lists.