time complexity merge sort

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 → Divide → और Divide → और Divide → और 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 : और Compare 38 और 27 → 27 smaller है → 27 पहले आएगा फिर 38 → Merge Result → Next merge : और → Final merge : और → Example Step-by-Step Example of Merge Sort Original Array : Step 1 : Divide (बाँटना) Original Array → Divide → और Divide → और Divide → और Step 2 : Merge (जोड़ना) Merge और Compare 38 और 27 → 27 smaller → पहले आएगा Merge Result → Merge और Compare 43 और 3 → 3 smaller → पहले आएगा Merge Result → Merge और Compare 27 और 3 → 3 smaller → first Compare 27 और 43 → 27 smaller → next Compare 38 और 43 → 38 smaller → next 43 → last Final Sorted Array → Step 3 : Result Original Array : Sorted Array : 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 होती है। 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 ज्यादा हो सकता है।

Merge Sort Algorithm

DCA के सभी नोट्स,
पुराने पेपर और महत्वपूर्ण प्रश्न उत्तर

PGDCA के सभी नोट्स,
पुराने पेपर और महत्वपूर्ण प्रश्न उत्तर

Merge Sort Algorithm

Start typing and press enter to search

DCA के सभी नोट्स, पुराने पेपर और महत्वपूर्ण प्रश्न उत्तर

PGDCA के सभी नोट्स, पुराने पेपर और महत्वपूर्ण प्रश्न उत्तर

DCA के सभी नोट्स,
पुराने पेपर और महत्वपूर्ण प्रश्न उत्तर

PGDCA के सभी नोट्स,
पुराने पेपर और महत्वपूर्ण प्रश्न उत्तर