Merge Sort is an efficient algorithm used to order/sort a list of elements in ascending or descending order. In the previous articles, we explored the intuition behind Merge Sort and the process of merging two sorted arrays. Now, let’s tie everything together and walk through how Merge Sort works step by step. We’ll focus on the high-level process without diving into code or pseudocode, keeping the explanation simple and intuitive.
Prerequisites:
The Core Idea: Divide, Conquer and Merge
Merge Sort is built on a simple yet powerful strategy:
- Keep dividing the problem into smaller parts until they become easy to solve.
- Solve the smallest subproblem (In the context of sorting, an array or list of size 1 is the smallest subproblem)
- Keep combining the solutions of each part to get the final answer.
This strategy is commonly known as Divide and Conquer. Let’s break it down the merge sort algorithm into three main steps:
- Divide the list into two halves
- If the list has only 1 element, it means that the list is already sorted. So just return it without dividing further (Conquer).
- Recursively sort each half (Back to step 1 for each list).
- Merge sorted lists of both the sorted halves into a single sorted list.
Recursively Dividing the List into Two Halves
Imagine you have an unsorted list of numbers, like this:
The first step is to divide the list into smaller halves. Merge Sort does this recursively until each sublist contains only one element. Here’s how it works:
-
Split the list into two halves:
-
Continue splitting each half:
-
Keep splitting until you can’t divide further:
At this point, every sublist has only one element. List with one element is a list which is already sorted. So the algorithm stops dividing when it reaches a list with single element and starts merging lists back into larger sorted lists.
Recursively Merging the Sorted Sub Lists
Now that the list has been divided into its smallest parts, the next step is to merge these sublists in sorted order. We can consider two sublists belonging to same parent and merge them together into a single sorted list. There are 8 sublists and after merging 2 sublists in groups, we create 4 sublists of length two and all the four sublists are individually sorted. Below is how this step looks like:
We now have 4 sorted sublists. We can again consider two sublists belonging to the same parent and merge them together into a single sorted list. Below is how this step looks like:
We now have just two sorted sublists and so we can merge both the sublists into a single list, which is the final sorted list we require.
In the next article, we’ll dive into the implementation of merge sort algorithm in python along with detailed explanation of how it works.