Merge Sort
Merge Sort is a comparison-based, divide-and-conquer sorting algorithm. It works by dividing the input array into smaller subarrays, sorting them individually, and then merging them back together to form a final sorted array.
Key Points:
- Divide and Conquer Approach: It splits the array into two halves again and again until each subarray has only one element (which is already sorted).
- Recursive Process: The sorting happens recursively. It keeps dividing the array until base case (1 element) is reached, then starts merging in sorted order.
- Merging Step: The real sorting happens in this step where two sorted subarrays are combined into one sorted array.
Why is it Called “Merge” Sort? Because it focuses on merging sorted subarrays, not just swapping like bubble or selection sort. This merging step is the heart of the algorithm. Working of Merge Sort (Step-by-Step) Merge Sort is a divide-and-conquer algorithm. It works in three main steps:
- Divide: Recursively divide the array into two halves until each subarray contains only one element.
- Conquer (Sort): Recursively sort each of the two halves.
- Combine (Merge): Merge the sorted halves to produce a new sorted array.
Given Array:[5, 3, 8, 4, 1, 12, 7]
Step 1: Divide the Array
[5, 3, 8, 4, 1, 12, 7]
→ [5, 3, 8] and [4, 1, 12, 7]
→ [5], [3, 8] and [4, 1], [12, 7]
→ [5], [3], [8] and [4], [1], [12], [7]
Step 2: Sort and Merge Each Part
Merge [3] and [8] → [3, 8]
Merge [5] and [3, 8] → [3, 5, 8]
Merge [4] and [1] → [1, 4]
Merge [12] and [7] → [7, 12]
Merge [1, 4] and [7, 12] → [1, 4, 7, 12]
Step 3: Final Merge
Merge [3, 5, 8] and [1, 4, 7, 12]
→ Compare 3 and 1 → 1
→ Compare 3 and 4 → 3
→ Compare 5 and 4 → 4
→ Compare 5 and 7 → 5
→ Compare 8 and 7 → 7
→ Compare 8 and 12 → 8
→ Remaining → 12
Final Sorted Array
[1, 3, 4, 5, 7, 8, 12]
Merge Sort code:
# Insertion Sort
def insertion_sort(arr):
n = len(arr)
# Start from second element
for i in range(1, n):
key = arr[i]
j = i - 1
# Move elements greater than key
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
# Insert key
arr[j + 1] = key
def print_array(arr):
for num in arr:
print(num, end=" ")
print()
arr = [12, 11, 13, 5, 6]
print("Before Sorting:")
print_array(arr)
insertion_sort(arr)
print("After Sorting:")
print_array(arr)
public class InsertionSort {
// Function to perform Insertion Sort
public static void insertionSort(int[] arr) {
int n = arr.length;
// Start from second element
for (int i = 1; i = 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
// Insert key
arr[j + 1] = key;
}
}
// Function to print array
public static void printArray(int[] arr) {
for (int num : arr)
System.out.print(num + " ");
System.out.println();
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6};
System.out.println("Before Sorting:");
printArray(arr);
insertionSort(arr);
System.out.println("After Sorting:");
printArray(arr);
}
}
#include <stdio.h>
void insertionSort(int arr[], int n) {
for (int i = 1; i = 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {12,11,13,5,6};
int n = 5;
printf("Before Sorting:\n");
printArray(arr, n);
insertionSort(arr, n);
printf("After Sorting:\n");
printArray(arr, n);
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
void insertionSort(vector<int>& arr) {
int n = arr.size();
for (int i = 1; i = 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
void printArray(vector<int> arr) {
for (int num : arr)
cout << num << " ";
cout << endl;
}
int main() {
vector<int> arr = {12,11,13,5,6};
cout << "Before Sorting:" << endl;
printArray(arr);
insertionSort(arr);
cout << "After Sorting:" << endl;
printArray(arr);
return 0;
}
| Case | Time Complexity | Explanation |
| Best Case | O (n log n) | Even if the array is already sorted, it still divides and merges. |
| Average Case | O (n log n) | Every time the array is divided into halves and merged systematically. |
| Worst Case | O (n log n) | Division and merging happen regardless of input order. |
Space Complexity:
- O(n)(Extra space is required to merge the divided arrays)
Note: Merge Sort is a divide and conquer algorithm. It’s efficient and consistent with time complexity O (n log n) in all cases. It is stable and preferred for large datasets, though it needs additional memory.