Merge Sort
Merge Sort एक comparison-based sorting algorithm है, जो divide and conquer technique का use करता है। इसे सबसे पहले John von Neumann ने 1945 में introduce किया था। इस algorithm में array को continuously divide किया जाता है, जब तक कि हर sub-array में केवल single element ना बचे। इसके बाद, इन sub-arrays को merge करके एक sorted array तैयार किया जाता है।
Key Points :
- यह stable sorting algorithm है, यानी original order maintain रहता है।
- यह एक recursive algorithm है।
- Time Complexity : O(n log n) (Best, Average, Worst)
- Space Complexity : O(n)
Working Principle (कैसे काम करता है?)
इसका working दो main steps में होता है :
1. Divide (बाँटना)
- सबसे पहले original array को दो halves (अलग अलग भाग) में divide किया जाता है।
- फिर प्रत्येक half को recursively divide किया जाता है, जब तक कि sub-array में एक ही element न रह जाए।
- Single element array हमेशा sorted माना जाता है।
Example :
Original Array → [38, 27, 43, 3]
- Divide →
[38,27]और[43,3] - Divide
[38,27]→[38]और[27] - Divide
[43,3]→[43]और[3]
2. Merge (जोड़ना)
- अब छोटे sub-arrays को merge करके sorted array बनाना शुरू होता है।
- Merge step में दो sorted sub-arrays को compare करके final sorted array बनाया जाता है।
- Compare करते समय ascending या descending order maintain किया जाता है।
Step-by-step Merge Example :
Sub-arrays : [38] और [27]
- Compare 38 और 27 → 27 smaller है → 27 पहले आएगा
- फिर 38 → Merge Result →
[27, 38]
Next merge : [43] और [3] → [3, 43]
Final merge : [27,38] और [3,43] → [3,27,38,43]
Example
Step-by-Step Example of Merge Sort
Original Array :[38, 27, 43, 3]
Step 1 : Divide (बाँटना)
Original Array →
[38, 27, 43, 3]Divide →
[38, 27]और[43, 3]
Divide
[38, 27]→[38]और[27]Divide
[43, 3]→[43]और[3]
Step 2 : Merge (जोड़ना)
Merge
[38]और[27]Compare 38 और 27 → 27 smaller → पहले आएगा
Merge Result →
[27, 38]
Merge
[43]और[3]Compare 43 और 3 → 3 smaller → पहले आएगा
Merge Result →
[3, 43]
Merge
[27, 38]और[3, 43]Compare 27 और 3 → 3 smaller → first
Compare 27 और 43 → 27 smaller → next
Compare 38 और 43 → 38 smaller → next
43 → last
Final Sorted Array →
[3, 27, 38, 43]
Step 3 : Result
Original Array : [38, 27, 43, 3]
Sorted Array : [3, 27, 38, 43]
Pseudo Code
MergeSort(arr[], left, right)
If left < right then
mid = (left + right) / 2
MergeSort(arr, left, mid) // Left half recursively sort
MergeSort(arr, mid + 1, right) // Right half recursively sort
Merge(arr, left, mid, right) // Merge two sorted halves
Applications of Merge Sort
- E-Commerce Websites : Flipkart, Amazon – Products को price, rating या popularity के हिसाब से sort करना।
- Banking & Finance : Paytm, SBI – Transaction history और statements efficiently sort करना।
- Government Portals : IRCTC, DigiLocker – Train schedules और document lists sort करना।
- Data Analytics & AI : ML datasets, research data – Large datasets को analysis के लिए ready करना।
- Big Data / Cloud Systems : Hadoop, Spark – Large volume data को efficiently manage करना।
- File Systems / External Sorting : Large logs, database records – RAM में न आने वाले data को sort करना।
- Real-time Applications : Flight schedules, sports leaderboards – Fast और accurate sorting देना।
Advantages of Merge Sort
- Stable Sorting
- Equal elements का original order maintain रहता है।
- Predictable Time Complexity
- Time complexity हमेशा O(n log n) रहती है, चाहे array sorted हो या unsorted।
- Works on Large Datasets
- Big Data या server applications में आसानी से use किया जा सकता है।
- Recursive & Elegant
- Divide and conquer approach clean और easy to understand होती है।
- Divide and conquer approach clean और easy to understand होती है।
Disadvantages of Merge Sort
- Extra Space Required
- यह in-place sorting algorithm नहीं है, इसलिए extra memory की जरूरत होती है।
- Slower for Small Arrays
- Small arrays के लिए Bubble Sort या Insertion Sort faster हो सकते हैं।
- Recursive Calls Overhead
- Recursive calls के कारण memory stack usage ज्यादा हो सकता है।
