Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 15

Merge Sort: Divide and Conquer

Recommended resources

Hello! Welcome to the third lesson in our module on Sorting and Searching Algorithms.

In our last two lessons, we explored the power of binary search, culminating in applying it to abstract "answer spaces." A common thread was the idea of repeatedly narrowing down a problem. Today, we'll formalize this with a powerful algorithmic paradigm: Divide and Conquer.

Our focus will be on Merge Sort, a classic sorting algorithm that perfectly embodies this strategy. You will learn how to implement Merge Sort and gain a deep understanding of its divide-and-conquer approach. This algorithm is a cornerstone of computer science and a frequent guest in competitive programming problems due to its predictable and efficient performance.

The Divide and Conquer Strategy

The "Divide and Conquer" strategy involves three main steps to solve a problem:

  1. Divide: Break the main problem into smaller, self-similar subproblems.
  2. Conquer: Solve the subproblems recursively. If a subproblem is small enough, solve it directly (this is the "base case").
  3. Combine: Merge the solutions of the subproblems to create the solution for the original problem.

Let's see how this applies specifically to sorting an array.

Merge Sort Algorithm

To start, let's read a concise definition of this strategy from Programiz. This will give you a formal framework for thinking about the algorithm.

Please read the sections 'Merge Sort Algorithm' and 'Divide and Conquer Strategy'. Focus on the definitions of the 'Divide', 'Conquer', and 'Combine' steps in the context of sorting an array.

As you read, Merge Sort divides an array into two halves, recursively sorts them, and then combines the sorted halves. The "base case" for the recursion is an array with one or zero elements, which is already considered sorted.

The following image provides a high-level visual of this process.

Merge Sort Divide and Conquer Example
This diagram shows an unsorted array being recursively split (the 'Divide' phase) until only single-element arrays remain. Then, these are progressively merged back together in sorted order (the 'Combine' phase) to produce the final sorted array.

The most interesting part of this process is the "Combine" step. How do you efficiently merge two already sorted arrays into one?

The Core of the Algorithm: The merge Step

The magic of Merge Sort lies in its merge function. This function takes two sorted subarrays and combines them into a single, larger sorted array. This is achieved using a simple and efficient two-pointer technique.

Imagine you have two sorted lists of numbers and an empty list for your result.

  • You place a pointer at the beginning of each sorted list.
  • You compare the two numbers the pointers are pointing to.
  • You take the smaller of the two, add it to your result list, and advance the pointer of the list you took it from.
  • You repeat this process until one of the lists is empty. Then, you simply append the remaining elements from the non-empty list to your result.

Let's watch a short video that illustrates this exact idea.

Merge Sort - Data Structures & Algorithms Tutorial Python #17

This clip from the 'codebasics' channel provides a clear, animated explanation of how to merge two sorted arrays.

Watch from the beginning to 02:01. Pay close attention to how the two pointers move as elements are compared and added to the final sorted array.

Test your understanding!

You are given two sorted arrays: left = [4, 8, 15] and right = [7, 9, 10].

Manually trace the two-pointer merge process. What is the state of the final merged array after the first three elements have been added?

Show answer
  1. Compare left[0] (4) and right[0] (7). 4 is smaller. Add 4 to the result. Result: [4].
  2. Compare left[1] (8) and right[0] (7). 7 is smaller. Add 7 to the result. Result: [4, 7].
  3. Compare left[1] (8) and right[1] (9). 8 is smaller. Add 8 to the result. Result: [4, 7, 8].

After three steps, the merged array is [4, 7, 8].

Now that you understand how to merge two sorted arrays, let's see how the recursive division sets up this merge step.

Merge Sort - Data Structures & Algorithms Tutorial Python #17

Continuing with the 'codebasics' video, let's see the full divide-and-conquer process in action.

Watch from 02:01 to 04:53. This part visualizes how an unsorted array is broken down to single elements and then built back up using the merge logic you just learned.

Implementing Merge Sort in Python

The implementation naturally splits into two functions:

  1. merge_sort(arr): The main recursive function that handles the "Divide" part.
  2. merge(left, right): A helper function that handles the "Combine" part.

This structure makes the code clean and easy to understand. The merge_sort function splits the array and calls itself on the two halves, and then uses the merge function to combine the results.

Implementing the Merge Sort Algorithm in Python

This article from Codecademy provides a fantastic, step-by-step breakdown of the Python code for both the merge_sort and merge functions.

Read the section 'Merge sort implementation in python'. It explains the base case, the recursive division, and the merge logic line by line. This will give you a solid mental model before seeing it coded live.

With that structure in mind, let's watch the implementation being coded from scratch.

Merge Sort - Data Structures & Algorithms Tutorial Python #17

This final segment from the 'codebasics' video will walk you through the Python implementation. The approach here is slightly different from the Codecademy article—it modifies the array in-place rather than returning a new one—but the core logic of dividing and merging is identical. This is a common implementation style in competitive programming.

Watch from 06:03 to 14:46. The first part (until 11:19) implements the merge_two_sorted_lists function. The second part (from 11:19) implements the recursive merge_sort function that uses it.

Complexity Analysis

Understanding an algorithm's efficiency is crucial. Merge Sort is highly valued for its consistency.

  • Time Complexity: O(n log n)

    • The log n part comes from the number of times you can divide the array in half. If you have an array of size 8, you divide it into 4s, then 2s, then 1s—that's 3 levels, and log₂(8) = 3.
    • The n part comes from the work done at each level. At every level of recursion, every single element must be processed and merged. This means n operations per level.
    • Multiplying them gives O(n log n). This holds true for the best, average, and worst cases, making Merge Sort very reliable.

  • Space Complexity: O(n)

    • This is the main trade-off of Merge Sort. During the merge step, we need temporary arrays to hold the left and right halves before merging them back into the main array. This auxiliary space requirement is proportional to the size of the input array.

The following video gives a great visual explanation of why the time complexity is O(n log n).

Sort an Array - Leetcode 912 - Python

This clip from NeetCode explains the time complexity by analyzing the recursion tree.

Watch from 06:43 to 08:40. Focus on how the work at each 'level' of the tree is O(n), and the 'height' of the tree is O(log n).

Conclusion

Congratulations on mastering Merge Sort! This is a significant step in building your algorithmic toolkit.

Key Takeaways:

  • Merge Sort is a classic Divide and Conquer algorithm.
  • The core logic is in the merge step, which efficiently combines two sorted arrays using a two-pointer approach.
  • It has a reliable and consistent time complexity of O(n log n) for all cases (best, average, and worst).
  • Its primary drawback is the O(n) space complexity required for the temporary arrays used during merging.

Up Next:
In the next lesson, we will explore Quicksort. It is another famous divide-and-conquer sorting algorithm, but it takes a different approach. Instead of doing the main work during the "Combine" step like Merge Sort, Quicksort does its work during the "Divide" step. Comparing these two algorithms will give you a much richer understanding of algorithmic design and trade-offs.