Merge sort algorithm: Sorting is a fundamental concept in computer science, and one of the most efficient and widely used sorting techniques is Merge Sort. Whether you’re preparing for coding interviews or building real-world software, understanding Merge Sort can boost your algorithmic thinking.
What is Merge Sort?
Merge Sort is a divide-and-conquer algorithm that works by breaking down a list into smaller chunks, sorting those pieces individually, and then merging them back together in the correct order. It’s known for its reliable performance, even with large datasets.
Key Characteristics:
- Stable Sort: Maintains the relative order of equal elements.
- Time Complexity: O(n log n) in all cases (best, average, worst).
- Space Complexity: O(n) due to the temporary arrays used for merging.
How Does Merge Sort Work?
Imagine you have a messy pile of cards. Instead of sorting them all at once, you divide them into smaller piles, sort each pile, and then combine the sorted piles into one organized deck. Merge Sort does exactly that, but with numbers (or any sortable data).
Step-by-Step Process:
- Divide the array into two halves.
- Recursively sort each half.
- Merge the sorted halves into a single sorted array.
Sorting plays a crucial role in organizing data efficiently. Among the various algorithms, Merge Sort stands out for its efficiency and reliability. Let’s break it down in the simplest way possible.
Example
Let’s say you have the following array:
[38, 27, 43, 3, 9, 82, 10]Your goal is to sort this array in ascending order using Merge Sort.
Step-by-step:
- Divide:
Split the array until each part has a single element:[38] [27] [43] [3] [9] [82] [10] - Sort and Merge:
- Merge
[38]and[27]→[27, 38] - Merge
[27, 38]and[43]→[27, 38, 43] - Merge
[3]and[9]→[3, 9], then merge with[82]→[3, 9, 82], and finally merge with[10]→[3, 9, 10, 82]
- Final Merge:
Merge[27, 38, 43]and[3, 9, 10, 82]→[3, 9, 10, 27, 38, 43, 82]
Intuition
Imagine you are sorting playing cards. It’s easier to sort two small piles and then combine them than to sort a large pile all at once. That’s what Merge Sort does.
- It divides the problem into smaller sub-problems.
- Solves each smaller problem (sorts each half).
- Then combines the solutions (merges sorted halves).
This divide-and-conquer strategy makes Merge Sort powerful and predictable.
Approach
Merge Sort follows a recursive strategy:
- Divide the array into two halves.
- Recursively apply merge sort to each half.
- Merge the two sorted halves into one.
Key Points:
- Uses extra space (temporary arrays).
- Always has time complexity of O(n log n).
- Performs well with large datasets and linked lists.
Pseudocode
Here’s the simplified pseudocode for Merge Sort:
Merge Sort Pseudocode
What’s the Goal?
We want to take an unsorted array and sort it in ascending order. Merge Sort does this by splitting the array, sorting the parts, and then merging them.
MergeSort(arr, left, right)
Explanation:
- arr[] – This is the array we want to sort.
- left – The starting index of the array.
- right – The ending index of the array.
Step-by-step:
- If left is smaller than right, it means we still have more than one element in the array.
- Find the middle point (to divide the array into two halves).
- Recursively sort the first half.
- Recursively sort the second half.
- Merge the two sorted halves.
It keeps calling itself (recursion) until each half has only one element. That’s when sorting begins.
Merge(arr, left, mid, right)
Explanation:
This function merges two already sorted halves of the array into one sorted array.
Step-by-step:
- Make two temporary arrays – one for the left part and one for the right part.
- Copy elements from the original array into these two parts.
- Start comparing the first elements from both halves:
- Put the smaller one back into the original array.
- Keep comparing and placing until one of the arrays is empty.
- If anything is left over in L or R, just copy it into the original array.
Real-Life Analogy
Think of Merge Sort like sorting pages of a book:
- You split the book in half.
- Ask two people to sort each half separately.
- Then you take both sorted stacks and combine them one page at a time in the correct order.
Visual Example
Suppose we want to sort the array:[38, 27, 43, 3, 9, 82, 10]
- Split into two halves:
[38, 27, 43]and[3, 9, 82, 10] - Keep splitting until you reach single-element arrays:
[38] [27] [43] [3] [9] [82] [10]
- Merge step-by-step:
[27, 38],[3, 43],[9, 10],[9, 10, 82]- Final result:
[3, 9, 10, 27, 38, 43, 82]
Merge Sort in Java
public class MergeSort {
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
public static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++];
} else {
arr[k++] = R[j++];
}
}
while (i < n1)
arr[k++] = L[i++];
while (j < n2)
arr[k++] = R[j++];
}
public static void main(String[] args) {
int[] arr = {38, 27, 43, 3, 9, 82, 10};
mergeSort(arr, 0, arr.length - 1);
for (int num : arr)
System.out.print(num + " ");
}
}
Merge Sort in C++
#include <iostream>
using namespace std;
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++) L[i] = arr[left + i];
for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
int main() {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, n - 1);
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
Merge Sort in C
#include <stdio.h>
void merge(int arr[], int left, int mid, int right) {
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for (i = 0; i < n1; i++) L[i] = arr[left + i];
for (j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
i = 0; j = 0; k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) arr[k++] = L[i++];
else arr[k++] = R[j++];
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
int main() {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, n - 1);
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
Merge Sort in Python
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
merge_sort(left)
merge_sort(right)
i = j = k = 0
# Merge the two halves
while i < len(left) and j < len(right):
if left[i] <= right[j]:
arr[k] = left[i]
i += 1
else:
arr[k] = right[j]
j += 1
k += 1
# Remaining elements
while i < len(left):
arr[k] = left[i]
i += 1
k += 1
while j < len(right):
arr[k] = right[j]
j += 1
k += 1
# Example usage
arr = [38, 27, 43, 3, 9, 82, 10]
merge_sort(arr)
print(arr)
Merge Sort in JavaScript
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(left, right) {
let result = [], i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result.push(left[i++]);
} else {
result.push(right[j++]);
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}
// Example usage
const arr = [38, 27, 43, 3, 9, 82, 10];
const sorted = mergeSort(arr);
console.log(sorted);
Merge Sort vs Bubble Sort
| Feature | Merge Sort | Bubble Sort |
|---|---|---|
| Approach | Divide and Conquer | Repeatedly swapping |
| Time Complexity | O(n log n) | O(n²) |
| Best Case | O(n log n) | O(n) (if optimized) |
| Stable? | Yes | Yes |
| Recursive? | Yes | No |
| Use Case | Large datasets | Teaching / simple examples |
| Extra Space? | Yes (O(n)) | No |
🔸 Merge Sort is way faster than Bubble Sort for large arrays.
Merge Sort vs Insertion Sort
| Feature | Merge Sort | Insertion Sort |
|---|---|---|
| Approach | Divide and Conquer | Builds final array one item at a time |
| Time Complexity | O(n log n) | O(n²) |
| Best Case | O(n log n) | O(n) (when array is sorted) |
| Stable? | Yes | Yes |
| Recursive? | Yes | No |
| Use Case | Large datasets | Small or nearly sorted arrays |
| Extra Space? | Yes | No |
🔸 Insertion Sort is good for small or nearly sorted arrays. Merge Sort is better for general use.
Merge Sort vs Selection Sort
| Feature | Merge Sort | Selection Sort |
|---|---|---|
| Approach | Divide and Conquer | Finds minimum each pass |
| Time Complexity | O(n log n) | O(n²) |
| Best Case | O(n log n) | O(n²) |
| Stable? | Yes | No |
| Recursive? | Yes | No |
| Use Case | General purpose sorting | Educational purposes |
| Extra Space? | Yes | No |
🔸 Selection Sort is simple but not efficient. Merge Sort wins in speed.
Merge Sort vs Quick Sort
| Feature | Merge Sort | Quick Sort |
|---|---|---|
| Approach | Divide and Conquer | Divide and Conquer |
| Time Complexity | O(n log n) | Average: O(n log n), Worst: O(n²) |
| Best Case | O(n log n) | O(n log n) |
| Stable? | Yes | No (unless modified) |
| Recursive? | Yes | Yes |
| Use Case | Linked lists or when stability is required | Faster on arrays, commonly used |
| Extra Space? | O(n) | O(log n) (in-place) |
🔸 Quick Sort is generally faster in practice but not stable. Merge Sort is more predictable.
Summary Table
| Sort | Time (Best) | Time (Worst) | Stable | Space | Suitable For |
|---|---|---|---|---|---|
| Merge Sort | O(n log n) | O(n log n) | ✅ | O(n) | Large, stable sorting |
| Quick Sort | O(n log n) | O(n²) | ❌ | O(log n) | Fast general purpose |
| Bubble Sort | O(n) | O(n²) | ✅ | O(1) | Educational, small sets |
| Insertion | O(n) | O(n²) | ✅ | O(1) | Nearly sorted data |
| Selection | O(n²) | O(n²) | ❌ | O(1) | Simple, not efficient |
Real-World Use Cases of Merge Sort
- External Sorting: Ideal for sorting huge files on disk where memory is limited.
- Linked Lists: Performs better than quicksort on linked lists.
- Parallel Processing: Merge Sort can be efficiently parallelized due to its divide-and-conquer nature.
Advantages and Disadvantages
Pros:
- Predictable time complexity (O(n log n)).
- Great for sorting linked lists.
- Stable sort.
Cons:
- Uses extra memory.
- Slower for small datasets compared to quicksort or insertion sort.
Basic-Level Interview Questions
- What is Merge Sort?
- Can you explain the Merge Sort algorithm in simple terms?
- What is the time and space complexity of Merge Sort?
- Best, worst, average case complexities?
- Is Merge Sort a stable sorting algorithm? Why?
- What is the difference between Merge Sort and Quick Sort?
- Which one is preferred and when?
- Does Merge Sort work in-place?
- If not, how much additional memory does it need?
- What do you mean by Divide and Conquer approach?
- Can you give a real-world analogy for it?
Intermediate-Level Questions
- Can you write the Merge Sort algorithm in any language of your choice?
- Explain the merge process in Merge Sort.
- How does the merging step maintain order?
- How is Merge Sort implemented on a linked list?
- Why is it more efficient in that case?
- How would you modify Merge Sort to count the number of inversions in an array?
- Can you implement Merge Sort iteratively (bottom-up approach)?
Advanced/Real-World Questions
- How would you handle very large datasets that don’t fit into memory using Merge Sort?
- External sorting techniques?
- How can you optimize the space complexity of Merge Sort?
- What are the cache performance issues in Merge Sort compared to Quick Sort?
- Where is Merge Sort used in real-world systems or libraries?
- (e.g., Timsort is based on Merge Sort + Insertion Sort)
- How would you parallelize Merge Sort in a multi-threaded system?
Bonus Conceptual Questions
- Why does Merge Sort have consistent O(n log n) time complexity regardless of input?
- Can you identify when Merge Sort is not the best option to use?
- Explain Merge Sort using recursion stack trace.
- What happens in each call?
- Why do some standard libraries prefer Quick Sort or Timsort over Merge Sort?
Thank you for exploring Merge Sort tutorials ! Stay ahead in embedded systems with expert insights, hands-on projects, and in-depth guides. Follow Embedded Prep for the latest trends, best practices, and step-by-step tutorials to enhance your expertise. Keep learning, keep innovating!
You can also Visit other tutorials of Embedded Prep
- What is eMMC (Embedded MultiMediaCard) memory ?
- Top 30+ I2C Interview Questions
- Bit Manipulation Interview Questions
- Structure and Union in c
- Little Endian vs. Big Endian: A Complete Guide
Special thanks to @embedded-prep for contributing to this article on Embedded Prep
Leave a Reply