Merge Sort: Divide, Conquer, Combine, Stable O(n log n) Notes in Hindi & English : मर्ज सॉर्ट: डिवाइड एंड कॉन्कर, रिकर्सिव मर्ज और O(n log n) और 20 महत्वपूर्ण MCQ प्रश्न (Rajasthan IT Exam)

Post a Comment

PGDCA, BCA, B-Tech, MCA, M-Tech, B.Sc computer science राजस्थान सूचना सहायक व कंप्यूटर शिक्षक विशेष नोट्स: इस अध्याय में हम Merge Sort: Divide, Conquer, Combine, Stable O(n log n) (मर्ज सॉर्ट: डिवाइड एंड कॉन्कर, रिकर्सिव मर्ज और O(n log n)) की संपूर्ण थ्योरी, मुख्य तकनीकी बिंदु, तुलनात्मक तालिका और विगत परीक्षाओं के पैटर्न पर आधारित 20 अति-महत्वपूर्ण बहुविकल्पीय प्रश्न (MCQs) विस्तृत हिंदी व अंग्रेजी व्याख्या सहित पढ़ेंगे।

Overview: Merge Sort applies Divide, Conquer, and Combine to guarantee Theta(n log n) time across all cases while maintaining strict stability, requiring O(n) auxiliary space on arrays and O(1) link space on linked lists.

अध्याय सार: मर्ज सॉर्ट डिवाइड, कॉन्कर और कंबाइन सिद्धांत पर कार्य करके सभी स्थितियों में Theta(n log n) समय व पूर्ण स्थिरता (Stability) सुनिश्चित करता है; इसमें एरे पर O(n) और लिंक्ड लिस्ट पर O(1) डेटा स्पेस लगता है।

Merge Sort: Divide, Conquer, Combine, Stable O(n log n): Detailed Notes & Architecture (मर्ज सॉर्ट: डिवाइड एंड कॉन्कर, रिकर्सिव मर्ज और O(n log n))

1. Three-Phase Divide, Conquer, and Combine Paradigm (तीन-चरणीय डिवाइड, कॉन्कर व कंबाइन प्रणाली)

[EN] Merge Sort recursively splits an array until single-element base subarrays (already sorted by definition) are reached. In the Divide phase, it computes mid = low + (high - low) / 2 in O(1) time. In the Conquer phase, it recursively sorts left half [low..mid] and right half [mid+1..high]. Finally, the Combine phase invokes a linear two-pointer merge() routine that weaves the two sorted subarrays into one sorted segment using temporary buffer arrays L and R.

[HI] मर्ज सॉर्ट एरे को तब तक दो भागों में बांटता है जब तक कि एक-एक तत्व के सब-एरे (जो स्वतः सॉर्टेड होते हैं) न बच जाएं। डिवाइड चरण O(1) में मध्य बिंदु mid निकालता है; कॉन्कर चरण बाएँ व दाएँ आधे भाग को रिकर्सिवली सॉर्ट करता है; और कंबाइन चरण दो-पॉइंटर मर्ज रूटीन द्वारा दोनों सॉर्टेड हिस्सों को मिलाकर एक क्रमित खंड तैयार करता है।

2. Recurrence Relation & Case-Invariant Theta(n log n) (रिकरेंस समीकरण व सभी स्थितियों में Theta(n log n))

[EN] Dividing an n-element array into two n/2 subproblems and merging them in Theta(n) produces the recurrence T(n) = 2T(n/2) + Theta(n). By Master Theorem Case 2 (where a = 2, b = 2, log_b(a) = 1 matches f(n) = Theta(n^1)), total time across all log2(n) recursion tree levels is Theta(n log n). Because standard Merge Sort always splits and merges regardless of input ordering, Best, Average, and Worst cases are all Theta(n log n) (unless a short-circuit check arr[mid] <= arr[mid+1] is explicitly added).

[HI] n आकार की समस्या को दो n/2 भागों में बांटने और Theta(n) में मर्ज करने से रिकरेंस T(n) = 2T(n/2) + Theta(n) प्राप्त होता है। मास्टर थ्योरम केस 2 के अनुसार रिकर्शन ट्री के सभी log2(n) स्तरों पर कुल कार्य Theta(n log n) आता है। मानक मर्ज सॉर्ट इनपुट के पहले से सॉर्टेड होने पर भी पूरा विभाजन और मर्ज चलाता है, इसलिए इसका बेस्ट, एवरेज व वर्स्ट केस तीनों Theta(n log n) होते हैं।

3. Space Trade-Off, Stability & Linked List Advantage (मेमोरी ट्रेड-ऑफ, स्थिरता व लिंक्ड लिस्ट पर श्रेष्ठता)

[EN] For contiguous arrays, Merge Sort is NOT in-place: merging requires an O(n) temporary buffer alongside O(log n) recursion stack frames, yielding O(n) total auxiliary space. However, Merge Sort is inherently STABLE whenever equal keys prioritize the left subarray via 'if (L[i] <= R[j])'. Moreover, for Linked Lists, Merge Sort can locate the middle using slow/fast pointers and merge strictly by relinking next pointers—making it the preferred O(n log n) linked-list sort with O(1) extra data space.

[HI] एरे के लिए मर्ज सॉर्ट इन-प्लेस नहीं होता क्योंकि मर्जिंग हेतु O(n) अस्थायी बफर और O(log n) स्टैक स्पेस (कुल O(n) स्पेस) चाहिए। मर्ज करते समय 'L[i] <= R[j]' (<= शर्त) लिखने से समान मानों में बाएँ हिस्से को प्राथमिकता मिलती है, जिससे यह पूर्णतः स्टेबल रहता है। लिंक्ड लिस्ट में मध्य नोड स्लो/फास्ट पॉइंटर से खोजकर केवल नेक्स्ट-पॉइंटर जोड़कर बिना अतिरिक्त एरे (O(1) डेटा स्पेस) के मर्ज किया जा सकता है।

4. External Sorting & Inversion Counting Applications (एक्सटर्नल सॉर्टिंग व इनवर्जन गिनती अनुप्रयोग)

[EN] When massive datasets exceed available RAM (residing on SSD/HDD/tape), External Merge Sort reads RAM-sized chunks, sorts each chunk in memory, and performs a k-way merge using sequential buffered disk streams—avoiding the slow random disk seeks of Quick Sort. Additionally, modifying the merge step to add (mid - i + 1) whenever R[j] < L[i] counts all array inversions cleanly in O(n log n) time.

[HI] जब विशाल डेटा RAM से बड़ा होकर हार्ड डिस्क पर रखा हो, तब एक्सटर्नल के-वे मर्ज सॉर्ट डेटा को छोटे भागों में RAM में सॉर्ट करके क्रमवार स्ट्रीम द्वारा मर्ज करता है, जिससे डिस्क सीक ओवरहेड बहुत कम रहता है। इसके अलावा, मर्ज के दौरान R[j] < L[i] मिलने पर (mid - i + 1) जोड़कर पूरे एरे के कुल इनवर्जन O(n log n) में गिने जा सकते हैं।

Syntax, Formula & Technical Example (Merge Sort: Divide, Conquer, Combine, Stable O(n log n))

void merge(int a[], int l, int m, int r) {
    int n1 = m - l + 1, n2 = r - m, L[n1], R[n2];
    for (int p = 0; p < n1; p++) L[p] = a[l + p];
    for (int q = 0; q < n2; q++) R[q] = a[m + 1 + q];
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2)
        a[k++] = (L[i] <= R[j]) ? L[i++] : R[j++]; // <= keeps stability
    while (i < n1) a[k++] = L[i++];
    while (j < n2) a[k++] = R[j++];
}

Merge Sort: Divide, Conquer, Combine, Stable O(n log n) Quick Reference & Comparison Table

Merge Sort FeatureTechnical SpecificationExam Key Insight
Time Complexity (All Cases)T(n) = 2T(n/2) + n => Theta(n log n)No O(n^2) worst-case degradation unlike Quick Sort
Array Auxiliary SpaceO(n) merge buffer + O(log n) stackNot an in-place algorithm on contiguous arrays
Linked List SuitabilityO(n log n) time with O(1) node link spaceBeats Quick Sort by avoiding random index access
External Disk SortingK-way sequential multi-chunk mergeOptimal when file size far exceeds physical RAM

Merge Sort: Divide, Conquer, Combine, Stable O(n log n) Top 20 Bilingual MCQs with Answers

Q1. What recurrence relation accurately defines standard Merge Sort time complexity?

(मानक मर्ज सॉर्ट की टाइम कॉम्प्लेक्सिटी को कौन सा रिकरेंस संबंध सही ढंग से दर्शाता है?)

(A) T(n) = 2T(n/2) + Theta(n)

(B) T(n) = T(n-1) + Theta(n)

(C) T(n) = T(n/2) + Theta(1)

(D) T(n) = 2T(n/2) + Theta(1)

Correct Answer: (A)

[EN] Merge Sort divides into two subproblems of size n/2 and combines them via an O(n) merge step.

[HI] मर्ज सॉर्ट समस्या को दो n/2 उप-समस्याओं में बांटता है और O(n) समय में दोनों को मर्ज करता है।

Q2. What is the worst-case time complexity of standard Merge Sort on an array of n elements?

(n तत्वों के एरे पर मानक मर्ज सॉर्ट की वर्स्ट-केस टाइम कॉम्प्लेक्सिटी क्या होती है?)

(A) O(n^2)

(B) O(n log n)

(C) O(n)

(D) O(log n)

Correct Answer: (B)

[EN] Unlike Quick Sort, Merge Sort always splits symmetrically at the midpoint, guaranteeing Theta(n log n) even in the worst case.

[HI] क्विक सॉर्ट के विपरीत मर्ज सॉर्ट हमेशा ठीक मध्य से विभाजन करता है, अतः वर्स्ट केस में भी समय O(n log n) ही रहता है।

Q3. What is the auxiliary space complexity of standard Merge Sort when sorting an array of size n?

(n आकार के एरे को सॉर्ट करते समय मानक मर्ज सॉर्ट की ऑक्सिलरी स्पेस कॉम्प्लेक्सिटी कितनी होती है?)

(A) O(n)

(B) O(n log n)

(C) O(log n)

(D) O(1)

Correct Answer: (A)

[EN] The merge buffer requires O(n) auxiliary space (which dominates the O(log n) recursion stack space).

[HI] मर्ज करने के लिए अस्थायी बफर एरे हेतु O(n) अतिरिक्त मेमोरी की आवश्यकता होती है (जो O(log n) स्टैक से बड़ी है)।

Q4. Which comparison operator inside merge() guarantees that Merge Sort remains STABLE?

(merge() फंक्शन के भीतर कौन सा तुलना ऑपरेटर मर्ज सॉर्ट की स्थिरता (Stability) सुनिश्चित करता है?)

(A) L[i] >= R[j]

(B) L[i] < R[j] (taking from right subarray on equality)

(C) L[i] <= R[j] (taking from left subarray on equality)

(D) L[i] != R[j]

Correct Answer: (C)

[EN] When L[i] == R[j], choosing L[i] first preserves the original relative order since L precedes R.

[HI] समान मान होने पर पहले बाएँ सब-एरे (L[i]) को चुनने से मूल क्रम सुरक्षित रहता है, इसलिए <= आवश्यक है।

Q5. Why is Merge Sort preferred over Quick Sort for sorting Singly Linked Lists?

(सिंगली लिंक्ड लिस्ट को सॉर्ट करने के लिए क्विक सॉर्ट की तुलना में मर्ज सॉर्ट को प्राथमिकता क्यों दी जाती है?)

(A) Quick Sort cannot partition linked lists at all

(B) Merge Sort requires zero pointer modifications

(C) Merge Sort accesses nodes sequentially and merges by relinking pointers without random indexing or O(n) buffer

(D) Merge Sort runs in O(n) time on linked lists

Correct Answer: (C)

[EN] Linked lists lack O(1) random access and allow O(1)-extra-data merging simply by rearranging next pointers.

[HI] लिंक्ड लिस्ट में रैंडम एक्सेस नहीं होता, जबकि मर्ज सॉर्ट क्रमिक नोड्स को केवल पॉइंटर जोड़कर बिना अतिरिक्त एरे के मर्ज कर देता है।

Q6. Given two sorted arrays of sizes m and n, what is the MAXIMUM number of element comparisons needed to merge them?

(m और n आकार के दो सॉर्टेड एरे को मर्ज करने में अधिकतम (Worst Case) कितनी तत्व तुलनाएँ लग सकती हैं?)

(A) m + n

(B) min(m, n)

(C) m + n - 1

(D) m * n

Correct Answer: (C)

[EN] Maximum comparisons occur when arrays interleave down to the last remaining element, leaving 1 element uncompared: m + n - 1.

[HI] जब दोनों एरे का अंतिम एक तत्व शेष रहे तब तक हर कदम पर तुलना होने से अधिकतम m + n - 1 तुलनाएँ लगती हैं।

Q7. Given two sorted arrays of sizes m and n, what is the MINIMUM number of comparisons needed to merge them?

(m और n आकार के दो सॉर्टेड एरे को मर्ज करने में न्यूनतम (Best Case) कितनी तत्व तुलनाएँ लगेंगी?)

(A) min(m, n)

(B) 1

(C) m + n - 1

(D) max(m, n)

Correct Answer: (A)

[EN] If all elements of the smaller array are strictly smaller than the first element of the larger array, only min(m, n) comparisons occur.

[HI] यदि छोटे एरे के सभी तत्व बड़े एरे के पहले तत्व से भी छोटे हों, तो छोटा एरे खत्म होते ही मात्र min(m, n) तुलनाओं में मर्ज पूरा हो जाता है।

Q8. Which sorting paradigm does External Sorting (sorting gigabytes of disk data with limited RAM) primarily rely on?

(कम RAM में गीगाबाइट्स डिस्क डेटा को सॉर्ट करने वाली 'एक्सटर्नल सॉर्टिंग' मुख्य रूप से किस एल्गोरिदम पर आधारित है?)

(A) Selection Sort

(B) In-place Quick Sort

(C) Binary Insertion Sort

(D) K-way Merge Sort

Correct Answer: (D)

[EN] Disk blocks are sorted into runs inside RAM and then sequentially streamed through a k-way merge.

[HI] डिस्क डेटा के टुकड़ों को RAM में सॉर्ट करके के-वे मर्ज सॉर्ट के क्रमिक I/O बफर द्वारा मिलाया जाता है।

Q9. How can Merge Sort count the number of inversions in an array in O(n log n) time?

(मर्ज सॉर्ट का उपयोग करके O(n log n) में कुल इनवर्जन (Inversions) कैसे गिने जा सकते हैं?)

(A) Add (j + 1) whenever L[i] <= R[j]

(B) Count total swaps performed during recursion

(C) Count total recursive merge calls

(D) Whenever R[j] < L[i] during merge, add (n1 - i) (remaining elements in left half) to the inversion count

Correct Answer: (D)

[EN] Because left half L[i..n1-1] is already sorted ascending, if R[j] < L[i], then R[j] forms an inversion with L[i] and every element after i in L.

[HI] चूंकि बायाँ आधा हिस्सा पहले से सॉर्टेड है, अतः R[j] < L[i] होने पर R[j] बाएँ हिस्से के शेष सभी (n1 - i) तत्वों के साथ इनवर्जन बनाता है।

Q10. How does Bottom-Up (Iterative) Merge Sort work without recursion?

(बॉटम-अप (इटरेटिव) मर्ज सॉर्ट बिना रिकर्शन के कैसे कार्य करता है?)

(A) It iteratively merges adjacent subarrays of size 1, then 2, 4, 8, ... doubling width each pass

(B) It finds the median pivot first

(C) It inserts one element from left to right

(D) It builds a Max-Heap bottom-up

Correct Answer: (A)

[EN] Bottom-up merge sort eliminates the O(log n) call stack by merging pairs of size 1, 2, 4, 8 up to n.

[HI] यह बिना रिकर्शन स्टैक के पहले 1-1, फिर 2-2, 4-4, 8-8 आकार के सब-एरे को आपस में मर्ज करता जाता है।

Q11. During recursive Merge Sort on an array of 8 elements, how many total 'merge' calls occur across the recursion tree?

(8 तत्वों के एरे पर रिकर्सिव मर्ज सॉर्ट के दौरान कुल कितनी बार 'merge()' फंक्शन कॉल होगा?)

(A) 15

(B) 8

(C) 4

(D) 7

Correct Answer: (D)

[EN] Each internal node of the binary split tree triggers 1 merge; an 8-leaf binary tree has 8 - 1 = 7 internal merge nodes.

[HI] रिकर्शन ट्री में n = 8 लीफ नोड्स को जोड़ने के लिए हमेशा n - 1 = 7 आंतरिक मर्ज नोड्स (कॉल) होते हैं।

Q12. What modification makes Merge Sort Adaptive (O(n) best case on already sorted input) without harming worst-case O(n log n)?

(किस छोटे से बदलाव से मानक मर्ज सॉर्ट पहले से सॉर्टेड इनपुट पर O(n) (एडैप्टिव) बन जाता है?)

(A) Skipping the merge call if arr[mid] <= arr[mid + 1]

(B) Picking a random mid index

(C) Replacing O(n) buffer with Insertion Sort only

(D) Running two merges from both ends

Correct Answer: (A)

[EN] If the maximum of left half <= minimum of right half, both halves are already ordered together; skipping merge saves linear copying.

[HI] यदि बाएँ भाग का अंतिम तत्व दाएँ के पहले तत्व से छोटा या बराबर (arr[mid] <= arr[mid+1]) हो, तो मर्ज न करने पर सॉर्टेड एरे में O(n) समय लगता है।

Q13. Python's built-in 'Timsort' (also used in Java for objects) is a hybrid of which two algorithms?

(Python का इनबिल्ट 'Timsort' (और Java में ऑब्जेक्ट सॉर्टिंग) किन दो एल्गोरिदम का हाइब्रिड संयोजन है?)

(A) Quick Sort and Heap Sort

(B) Selection Sort and Counting Sort

(C) Merge Sort and Insertion Sort

(D) Bubble Sort and Radix Sort

Correct Answer: (C)

[EN] Timsort detects sorted runs, extends short runs with Insertion Sort, and merges runs stably using optimized Merge Sort.

[HI] Timsort वास्तविक डेटा में मौजूद प्राकृतिक सॉर्टेड रन्स (Runs) को इंसर्शन सॉर्ट और मर्ज सॉर्ट के स्थिर संयोजन से सॉर्ट करता है।

Q14. Which statement accurately compares Merge Sort and Quick Sort on typical in-memory primitive arrays?

(सामान्य RAM में प्रिमिटिव एरे सॉर्टिंग पर मर्ज सॉर्ट और क्विक सॉर्ट की सही तुलना कौन सी है?)

(A) Merge Sort is faster in practice on small primitives

(B) Merge Sort always uses less RAM than Quick Sort on arrays

(C) Quick Sort is stable while Merge Sort is unstable

(D) Quick Sort is usually faster in practice due to in-place O(1) data buffer and cache locality, though Merge Sort guarantees O(n log n) worst case and stability

Correct Answer: (D)

[EN] Quick Sort's in-place sequential writes avoid O(n) auxiliary allocation and copy overhead.

[HI] RAM में प्रिमिटिव एरे के लिए क्विक सॉर्ट कैश लोकैलिटी व इन-प्लेस प्रकृति से व्यावहारिक रूप से तेज होता है, जबकि मर्ज सॉर्ट स्थिरता और गारंटीड O(n log n) देता है।

Q15. Which statement is NOT true about standard Merge Sort?

(मानक मर्ज सॉर्ट के बारे में इनमें से कौन सा कथन सत्य नहीं है?)

(A) Its worst-case time complexity is O(n log n)

(B) It uses the Divide and Conquer strategy

(C) It is a stable sorting algorithm

(D) It is an in-place sorting algorithm with O(1) auxiliary space on arrays

Correct Answer: (D)

[EN] Standard array Merge Sort requires O(n) extra buffer memory, so it is NOT in-place.

[HI] एरे पर मानक मर्ज सॉर्ट O(n) अतिरिक्त बफर लेता है, इसलिए यह O(1) स्पेस वाला इन-प्लेस एल्गोरिदम नहीं है।

Q16. When sorting an array of size n = 1,000,000 using Merge Sort, approximately how deep is the recursion call stack?

(n = 1,000,000 आकार के एरे पर मर्ज सॉर्ट चलाने पर रिकर्शन कॉल स्टैक की गहराई लगभग कितनी होगी?)

(A) About 1,000 levels (O(sqrt(n)))

(B) About 20 levels (O(log n))

(C) Exactly 1 level

(D) About 1,000,000 levels (O(n))

Correct Answer: (B)

[EN] Each recursive descent halves n, reaching size 1 in ceil(log2(10^6)) = 20 stack frames.

[HI] हर चरण में आकार आधा होने से कॉल स्टैक की अधिकतम गहराई log2(10^6) ≈ 20 स्तर ही रहती है।

Q17. Within Merge Sort: Divide, Conquer, Combine, Stable O(n log n), which merge sort feature directly maps to: "T(n) = 2T(n/2) + n => Theta(n log n)"?

(Merge Sort: Divide, Conquer, Combine, Stable O(n log n) में कौन सा Merge Sort Feature सीधे "T(n) = 2T(n/2) + n => Theta(n log n)" से संबंधित है?)

(A) Linked List Suitability

(B) Array Auxiliary Space

(C) External Disk Sorting

(D) Time Complexity (All Cases)

Correct Answer: (D)

[EN] In Merge Sort: Divide, Conquer, Combine, Stable O(n log n), 'Time Complexity (All Cases)' handles 'T(n) = 2T(n/2) + n => Theta(n log n)' (No O(n^2) worst-case degradation unlike Quick Sort).

[HI] Merge Sort: Divide, Conquer, Combine, Stable O(n log n) में 'Time Complexity (All Cases)' का कार्य/विवरण 'T(n) = 2T(n/2) + n => Theta(n log n)' (No O(n^2) worst-case degradation unlike Quick Sort) है।

Q18. Which option accurately describes 'Array Auxiliary Space' in Merge Sort: Divide, Conquer, Combine, Stable O(n log n)?

(Merge Sort: Divide, Conquer, Combine, Stable O(n log n) के संदर्भ में 'Array Auxiliary Space' की सही विशेषता कौन सी है?)

(A) O(n) merge buffer + O(log n) stack

(B) T(n) = 2T(n/2) + n => Theta(n log n)

(C) K-way sequential multi-chunk merge

(D) O(n log n) time with O(1) node link space

Correct Answer: (A)

[EN] 'Array Auxiliary Space' provides 'O(n) merge buffer + O(log n) stack' — key point: Not an in-place algorithm on contiguous arrays.

[HI] 'Array Auxiliary Space' का मुख्य विवरण 'O(n) merge buffer + O(log n) stack' है (Not an in-place algorithm on contiguous arrays)।

Q19. In Merge Sort: Divide, Conquer, Combine, Stable O(n log n), identify the correct parameter for the specification: "O(n log n) time with O(1) node link space".

(Merge Sort: Divide, Conquer, Combine, Stable O(n log n) में "O(n log n) time with O(1) node link space" विवरण किस विकल्प के लिए सही है?)

(A) Linked List Suitability

(B) Time Complexity (All Cases)

(C) Array Auxiliary Space

(D) External Disk Sorting

Correct Answer: (A)

[EN] 'Linked List Suitability' corresponds to 'O(n log n) time with O(1) node link space' (Beats Quick Sort by avoiding random index access).

[HI] 'Linked List Suitability' का संबंध 'O(n log n) time with O(1) node link space' (Beats Quick Sort by avoiding random index access) से है।

Q20. Considering Merge Sort: Divide, Conquer, Combine, Stable O(n log n), what key behavior defines 'External Disk Sorting'?

(Merge Sort: Divide, Conquer, Combine, Stable O(n log n) में 'External Disk Sorting' की मुख्य भूमिका या मान क्या है?)

(A) O(n log n) time with O(1) node link space

(B) K-way sequential multi-chunk merge

(C) T(n) = 2T(n/2) + n => Theta(n log n)

(D) O(n) merge buffer + O(log n) stack

Correct Answer: (B)

[EN] 'External Disk Sorting' represents 'K-way sequential multi-chunk merge' (Optimal when file size far exceeds physical RAM).

[HI] 'External Disk Sorting' का अर्थ/मान 'K-way sequential multi-chunk merge' है (Optimal when file size far exceeds physical RAM)।

Merge Sort: Divide, Conquer, Combine, Stable O(n log n) — Exam FAQs

Q1: Why is Merge Sort NOT considered an in-place algorithm on arrays?

एरे पर मर्ज सॉर्ट को इन-प्लेस (In-Place) एल्गोरिदम क्यों नहीं माना जाता?

[EN] Standard array merging needs O(n) temporary extra memory to hold the two halves while writing sorted output back, exceeding the O(1) or O(log n) in-place threshold.

[HI] दो सॉर्टेड खंडों को सुरक्षित मर्ज करने के लिए O(n) अतिरिक्त अस्थायी बफर एरे बनाना पड़ता है, इसलिए यह O(1) स्थान वाला इन-प्लेस एल्गोरिदम नहीं है।

Q2: When should I choose Merge Sort over Quick Sort?

क्विक सॉर्ट की बजाय मर्ज सॉर्ट कब चुनना चाहिए?

[EN] Choose Merge Sort when stability of equal keys is mandatory, when worst-case O(n log n) predictability is critical, when sorting linked lists, or when sorting huge disk files externally.

[HI] जब समान कुंजियों की स्थिरता (Stability) अनिवार्य हो, वर्स्ट-केस में O(n log n) गारंटी चाहिए हो, लिंक्ड लिस्ट सॉर्ट करनी हो या डिस्क पर विशाल डेटा एक्सटर्नल सॉर्ट करना हो।

Q3: Is Merge Sort an online algorithm?

क्या मर्ज सॉर्ट एक ऑनलाइन एल्गोरिदम है?

[EN] No. Standard Merge Sort requires access to the dataset halves upfront to split and merge systematically, unlike Insertion Sort which absorbs live streaming items one by one.

[HI] नहीं। मानक मर्ज सॉर्ट को विभाजन व मर्ज के लिए पूरा डेटा चाहिए होता है, जबकि इंसर्शन सॉर्ट एक-एक कर आने वाले लाइव डेटा को तुरंत सॉर्ट कर सकता है।

Related Posts

  • Loading related posts...

Post a Comment

Search Topic Notes & 20 MCQs (Hindi / English)