← Back to DSA Course | Chapter 9: Sorting Algorithms | Lesson 4 of 9

Merge Sort क्या है

Merge sort homework के एक बड़े pile को बार-बार आधा split करने जैसा है जब तक हर pile एक paper न हो, फिर छोटे sorted piles को वापस एक साथ merge करना।

In this page:

  1. Basic Idea
  2. Step by Step
  3. Small Array
  4. Practice
  5. Summary
Syntax
markup 
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

Basic Idea

Merge sort array को recursively आधा split करता है जब तक हर piece में सिर्फ एक element न हो, फिर उन pieces को sorted order में वापस merge करता है — एक classic divide-and-conquer strategy जहां hard work merge के दौरान होता है, split के दौरान नहीं।

उदाहरण: Basic Idea

#include <iostream>
using namespace std;
void merge(int arr[], int l, int m, int r) {
	int n1 = m - l + 1, n2 = r - m, L[10], R[10];
	for (int i = 0; i < n1; i++) L[i] = arr[l + i];
	for (int i = 0; i < n2; i++) R[i] = arr[m + 1 + i];
	int i = 0, j = 0, k = l;
	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 l, int r) {
	if (l >= r) return;
	int m = (l + r) / 2;
	mergeSort(arr, l, m);
	mergeSort(arr, m + 1, r);
	merge(arr, l, m, r);
}
int main() {
	int arr[] = {5, 1, 4, 2, 8};
	mergeSort(arr, 0, 4);
	for (int x : arr) cout << x << " ";
	return 0;
}
public class Main {
	static void merge(int[] arr, int l, int m, int r) {
		int n1 = m - l + 1, n2 = r - m;
		int[] L = new int[n1], R = new int[n2];
		for (int i = 0; i < n1; i++) L[i] = arr[l + i];
		for (int i = 0; i < n2; i++) R[i] = arr[m + 1 + i];
		int i = 0, j = 0, k = l;
		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++];
	}
	static void mergeSort(int[] arr, int l, int r) {
		if (l >= r) return;
		int m = (l + r) / 2;
		mergeSort(arr, l, m);
		mergeSort(arr, m + 1, r);
		merge(arr, l, m, r);
	}
	public static void main(String[] args) {
		int[] arr = {5, 1, 4, 2, 8};
		mergeSort(arr, 0, 4);
		System.out.println(java.util.Arrays.toString(arr));
	}
}
def merge(arr, l, m, r):
    left = arr[l:m + 1]
    right = arr[m + 1:r + 1]
    i = j = 0
    k = l
    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
    while i < len(left):
        arr[k] = left[i]; i += 1; k += 1
    while j < len(right):
        arr[k] = right[j]; j += 1; k += 1

def merge_sort(arr, l, r):
    if l >= r:
        return
    m = (l + r) // 2
    merge_sort(arr, l, m)
    merge_sort(arr, m + 1, r)
    merge(arr, l, m, r)

arr = [5, 1, 4, 2, 8]
merge_sort(arr, 0, 4)
print(arr)
#include <stdio.h>
void merge(int arr[], int l, int m, int r) {
	int n1 = m - l + 1, n2 = r - m, L[10], R[10];
	for (int i = 0; i < n1; i++) L[i] = arr[l + i];
	for (int i = 0; i < n2; i++) R[i] = arr[m + 1 + i];
	int i = 0, j = 0, k = l;
	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 l, int r) {
	if (l >= r) return;
	int m = (l + r) / 2;
	mergeSort(arr, l, m);
	mergeSort(arr, m + 1, r);
	merge(arr, l, m, r);
}
int main() {
	int arr[] = {5, 1, 4, 2, 8};
	mergeSort(arr, 0, 4);
	for (int i = 0; i < 5; i++) printf("%d ", arr[i]);
	return 0;
}

Step by Step

Recursive split array को आधा करता रहता है जब तक यह आगे divide न हो सके; असली sorting work तब होता है जब पहले से sorted halves के pairs दोनों halves के front elements में से छोटा बार-बार लेकर वापस merge होते हैं।

उदाहरण: Step by Step

#include <iostream>
using namespace std;
int main() {
	cout << "Split [5,1,4,2] -> [5,1] [4,2] -> [5] [1] [4] [2] -> merge back up sorted";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		System.out.println("Split [5,1,4,2] -> [5,1] [4,2] -> [5] [1] [4] [2] -> merge back up sorted");
	}
}
print("Split [5,1,4,2] -> [5,1] [4,2] -> [5] [1] [4] [2] -> merge back up sorted")
#include <stdio.h>
int main() {
	printf("Split [5,1,4,2] -> [5,1] [4,2] -> [5] [1] [4] [2] -> merge back up sorted");
	return 0;
}

Small Array

दो छोटी sorted halves जैसे [1, 4] और [2, 3] पर merge step trace करना बिल्कुल दिखाता है कि front elements compare करना और एक समय में एक pointer आगे बढ़ाना कैसे बिना कुछ भी फिर से sort किए एक single sorted sequence produce करता है।

उदाहरण: Small Array

#include <iostream>
using namespace std;
int main() {
	int L[] = {1, 4}, R[] = {2, 3}, merged[4];
	int i = 0, j = 0, k = 0;
	while (i < 2 && j < 2) merged[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
	while (i < 2) merged[k++] = L[i++];
	while (j < 2) merged[k++] = R[j++];
	for (int x : merged) cout << x << " ";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int[] L = {1, 4}, R = {2, 3}, merged = new int[4];
		int i = 0, j = 0, k = 0;
		while (i < 2 && j < 2) merged[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
		while (i < 2) merged[k++] = L[i++];
		while (j < 2) merged[k++] = R[j++];
		System.out.println(java.util.Arrays.toString(merged));
	}
}
L, R = [1, 4], [2, 3]
merged = []
i = j = 0
while i < 2 and j < 2:
    if L[i] <= R[j]:
        merged.append(L[i]); i += 1
    else:
        merged.append(R[j]); j += 1
merged += L[i:] + R[j:]
print(merged)
#include <stdio.h>
int main() {
	int L[] = {1, 4}, R[] = {2, 3}, merged[4];
	int i = 0, j = 0, k = 0;
	while (i < 2 && j < 2) merged[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
	while (i < 2) merged[k++] = L[i++];
	while (j < 2) merged[k++] = R[j++];
	for (int x = 0; x < 4; x++) printf("%d ", merged[x]);
	return 0;
}

Practice

चूंकि merge sort evenly split करता है और प्रति level fixed मात्रा में merge work करता है, इसका total running time input के initial order की परवाह किए बिना predictable रहता है — दोनों एक sorted और एक reverse-sorted array पर इसे trace करने की कोशिश करें यह देखने के लिए कि merge steps दोनों तरह से वही रहते हैं।

उदाहरण: Practice

#include <iostream>
using namespace std;
int main() {
	int n = 8;
	cout << "Merge sort on " << n << " elements always does the same fixed amount of work per level";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int n = 8;
		System.out.println("Merge sort on " + n + " elements always does the same fixed amount of work per level");
	}
}
n = 8
print("Merge sort on", n, "elements always does the same fixed amount of work per level")
#include <stdio.h>
int main() {
	int n = 8;
	printf("Merge sort on %d elements always does the same fixed amount of work per level", n);
	return 0;
}

Summary

Merge sort हर case में (best, average, और worst) O(n log n) time की गारंटी देता है, जो bubble, selection, और insertion sort के O(n²) की तुलना में एक meaningful improvement है — tradeoff यह है कि merge sort को temporary merged arrays के लिए O(n) extra space चाहिए।

उदाहरण: Summary

#include <iostream>
using namespace std;
int main() {
	cout << "Merge sort: guaranteed O(n log n) in best, average, and worst case";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		System.out.println("Merge sort: guaranteed O(n log n) in best, average, and worst case");
	}
}
print("Merge sort: guaranteed O(n log n) in best, average, and worst case")
#include <stdio.h>
int main() {
	printf("Merge sort: guaranteed O(n log n) in best, average, and worst case");
	return 0;
}
Related Topics

K Sorted Lists को Merge करना · दो Sorted Lists को Merge करना · Insertion Sort क्या है · Quick Sort क्या है

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. बड़े indexes के साथ mid = (l + r) / 2 compute करना जहां l + r overflow कर सकता है (l + (r - l) / 2 उपयोग करें)।
  2. दूसरा half खत्म होने के बाद एक half के बचे elements copy करना भूल जाना।
  3. दोनों halves में mid के साथ recurse करना, जैसे sort(l, mid) और sort(mid, r), इसलिए ranges overlap करती हैं और यह कभी terminate नहीं होता।
🔒

Chapter Quiz — Complete all 9 topics to unlock

0/9 topics done

Complete these topics first:

← Previous Lesson Insertion Sort Next Lesson → Quick Sort

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.