Implementing the Merge Sort Algorithm in Python

Sorting is one of the most fundamental problems in computer science. Whether it’s organizing a to-do list, ranking search results, or arranging numbers in order, efficient sorting is important for handling large amounts of data. In this tutorial, we will explore how to implement merge sort in Python, a powerful sorting algorithm that uses a divide-and-conquer approach. We’ll learn how it works and how to implement it in Python and discuss its real-world applications.

What is merge sort?

Merge sort is a popular sorting algorithm that follows the divide-and-conquer approach. Instead of sorting the entire list at once, it breaks the problem into smaller pieces. The algorithm works by:

• Dividing the array into two halves recursively until each piece has just one element.
• Sorting the smaller parts.
• Merging the sorted halves back together in order, ensuring the result is a fully sorted array.

One of the reasons merge sort is widely used is its predictable efficiency. Unlike some other sorting algorithms that struggle in the worst case, merge sort consistently operates with a time complexity of O(n log n) across all inputs. We will compare merge sort with other algorithms in the following sections.

While merge sort may not always be the fastest option for small datasets due to its additional memory usage, it excels in sorting large datasets and linked lists where other algorithms might slow down.

But how exactly does the merge sort achieve it’s consistent performance? Let’s break down the step-by-step process that makes merge sort work.

How does merge sort work?

As we discussed, merge sort follows a divide-and-conquer approach. At its core, merge sort relies on two key operations:

• Dividing the array into smaller subarrays
• Merging those subarrays back together in sorted order

Let’s walk through these steps in detail:

1. Divide phase

   The algorithm starts by repeatedly splitting the input array into halves. First, the main array is divided into two equal (or nearly equal) parts. Then, each of those parts is further divided into two. This division continues recursively until we reach subarrays containing only a single element. By definition, a one-element array is already sorted.

2. Conquer phase (Merging)

   Once we have our single-element subarrays, we combine them in a sorted manner. The merging process compares elements from two sorted subarrays and builds a new, larger sorted array from them. For each pair of subarrays, we:

   • Compare the first elements of both arrays
   • Select the smaller element and add it to our result array
   • Move to the next element in the array that contributed the smaller element
   • Repeat until all elements from both arrays have been processed

3. Combine phase

   As the merging continues, we work our way back up through the recursion tree. Each merge operation produces larger and larger sorted subarrays. What starts as merging pairs of single elements grows to merging arrays of 2 elements, then 4, then 8, and so on. Each merged result maintains its sorted property, ensuring that by the time we reach the final merge, we have a completely sorted array.

Example

Let’s visualize this process with a simple 5-element array:

[38, 27, 43, 3, 9] 

to clipboard
Copy to clipboard

Step 1: Divide the array

We start by splitting the array in half and continue splitting until we have individual elements:

At this point, we’ve broken our array down into subarrays with single elements. A single-element array is already sorted by definition.

Step 2: Merge subarrays in sorted order

Now we start merging these single elements back together in sorted order:

First, we merge [38] and [27]. To merge these arrays:

• Compare 38 and 27
• 27 is smaller, so it goes first
• 38 remains, so it goes next

Result:

[3] and [9] are already sorted. Next, we merge [43] with [3, 9]:

Here’s how this merge works:

• Compare 43 and 3: 3 is smaller, the result so far: [3]
• Compare 43 and 9: 9 is smaller, the result so far: [3, 9]
• Only 43 remains, so add it to the result

Result:

Finally, we merge the remaining two sorted subarrays. For this final merge:

• Compare 27 and 3: 3 is smaller, the result so far: [3]
• Compare 27 and 9: 9 is smaller, the result so far: [3, 9]
• Compare 27 and 43: 27 is smaller, the result so far: [3, 9, 27]
• Compare 38 and 43: 38 is smaller, the result so far: [3, 9, 27, 38]
• Only 43 remains, so add it to the result

Final result:

And that’s it! Our array is now fully sorted.

Time and space complexity

Let’s understand the efficiency of merge sort by analyzing its time and space complexity.

Time complexity of merge sort

Merge sort consistently operates with time complexity of O(n log n), making it more efficient than algorithms like bubble sort or insertion sort, which can take O(n²) in the worst case. Here’s how it’s time complexity plays out in different scenarios:

• Best Case (O(n log n)): Even if the input is already sorted, merge sort still follows the same divide-and-conquer approach, recursively splitting and merging the array. The operations remain the same, leading to O(n log n) complexity.
• Average Case (O(n log n)): Regardless of the input order, the algorithm always divides the array into halves and merges them in a structured manner. Since this process occurs in log n levels, with each level requiring O(n) operations to merge elements, the total complexity remains O(n log n).
• Worst Case (O(n log n)): When the input is in the worst possible order (such as reverse order), merge sort still executes in the same structured way. Unlike quick sort, which can degrade to O(n²) in the worst case, merge sort maintains a steady O(n log n) performance.

Space complexity of merge sort

While merge sort is efficient in terms of time, it comes with an extra cost in terms of space. The algorithm requires additional memory to store the divided subarrays during merging, leading to a space complexity of O(n). This extra space holds temporary arrays while merging elements back together.

For recursive implementations, merge sort also has an O(log n) stack space overhead due to recursive function calls. However, the major space usage comes from the auxiliary arrays needed during merging. This makes merge sort less ideal for memory-constrained environments compared to in-place sorting algorithms like Quick Sort or Heap Sort.

Merge sort implementation in python

Let’s break down the merge sort algorithm into smaller, easy-to-understand parts. We’ll walk through each function and explain exactly what it does.

def merge_sort(arr):  
  # Base case: a list of 0 or 1 elements is 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 both halves 
  left_half = merge_sort(left_half) 
  right_half = merge_sort(right_half) 
 
  # Merge the sorted halves 
  return merge(left_half, right_half) 

to clipboard
Copy to clipboard

The above function is our primary function that implements the merge sort algorithm. Let’s understand each part:

• Base case: The first thing we do is check if our list has 0 or 1 elements. If it does, we simply return it since a list with a single element is already sorted! This is where our recursion will eventually stop.
• Dividing the array: We find the middle point of our array using integer division (//). Then we split our original array into two halves - everything before the middle point goes into left_half, and everything from the middle point onwards goes into right_half.
• Recursive sorting: We call the same merge_sort function on each half. This means each half will be further divided until we reach lists with single elements; then, those will be merged back up in sorted order.
• Merging: Once both halves are sorted, we combine them using our merge function to get a completely sorted array.

Next is the merge() function:

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

    # Compare elements from both lists and add the smaller one to the result
    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

to clipboard
Copy to clipboard

This first part of our merge function sets up the comparison logic:

• We create an empty list called result that will hold our merged, sorted elements.
• We initialise two pointers, i and j, to keep track of our position in the left and right lists.
• The while loop continues until we reach the end of either list.
• Inside the loop, we compare the current elements from both lists (left[i] and right[j]).
• We take the smaller element, add it to our result, and move the corresponding pointer forward.

Now for the second part of the merge() function:

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

    # Compare elements from both lists and add the smaller one to the result
    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

    # Second Part
    while i < len(left):
        result.append(left[i])
        i += 1

    # Add any remaining elements from the right list
    while j < len(right):
        result.append(right[j])
        j += 1

    return result

to clipboard
Copy to clipboard

After our first loop, one of the lists might still have elements left. These remaining elements are already sorted among themselves. The first while loop adds any remaining elements from the left list. The second while loop adds any remaining elements from the right list.

Finally, we return our completely merged and sorted list.

Now that we’ve explored the implementation details of merge sort, let’s step back and look at the bigger picture. Understanding when to use merge sort compared to other algorithms is crucial for making informed decisions in real-world programming scenarios.

Merge sort vs other sorting algorithms

Let’s compare merge sort with other sorting algorithms to understand its strengths and limitations:

As we’ve examined the inner workings of merge sort and compared it with other sorting algorithms, let’s now turn our attention to real-world applications.

Applications of merge sort

Merge sort is widely used in many real-world applications because of its consistent performance and unique properties:

• Sorting Large Datasets
  • Used in big data frameworks for massive dataset processing.
  • Implemented in financial systems for chronological order transactions.
• External Sorting
  • Ideal for data too large for memory.
  • Applied in log processing for large server logs.
• Sorting Linked Lists
  • Best for linked list sorting due to sequential access.
  • Rearranged pointers efficiently without extra memory.
• Database Algorithms
  • Powers index creation in database systems.
  • Employed in merge joins to combine sorted data.

Conclusion

Merge sort is a fundamental algorithm that plays a crucial role in the software industry. In this article, we learned that:

• Merge sort illustrates the benefits of breaking problems into smaller parts for efficient solutions.
• It guarantees O(n log n) time complexity, ensuring reliable performance regardless of input order.
• It requires O(n) additional memory but offers stability and efficiency on large datasets.
• Merge sort is essential for various applications, including database systems and big data processing.

If you’re interested in learning about algorithms, consider taking this free course called Learn Data Structures and Algorithms with Python on Codecademy.