Merge sort: stable merge और लागत
लक्ष्य और पूर्वज्ञान
पहले growth/bounds तथा insertion/selection-sort के मौजूदा पाठ पढ़ें। Sorted runs merge करना, invariant सिद्ध करना, समान keys का क्रम जाँचना और time/extra space निकालना सीखें। Array zero-indexed है; [l,r) में r शामिल नहीं। हर comparison और move O(1) है।
1. Divide, solve, combine
Length शून्य या एक हो तो लौटें। अन्यथा m=l+floor((r-l)/2) निकालें; [l,m) और [m,r) को recursively sort करके merge करें। केवल दोनों sorted halves जोड़ना पर्याप्त नहीं: [2,8] के बाद [1,5] लगाने से sorted array नहीं बनता।
अलग temporary array B लें। i=l, j=m, k=0 रखें। दोनों runs में records बचने तक heads compare करें और छोटा B[k] में डालें; संबंधित input pointer और k बढ़ाएँ। बराबरी पर left record लें। एक run समाप्त होने पर दूसरे का बचा suffix जोड़ें, फिर B को A[l:r] में copy करें। इसी विधि में unread input के ऊपर लिखना गलत है।
while i < m and j < r:
if A[i].key <= A[j].key:
B[k] = A[i]; i = i + 1
else:
B[k] = A[j]; j = j + 1
k = k + 1
while i < m: B[k] = A[i]; i = i+1; k = k+1
while j < r: B[k] = A[j]; j = j+1; k = k+1
for t = 0,...,r-l-1: A[l+t] = B[t]2. Invariant और stability
हर main-loop शुरुआत में B[0:k], consumed prefixes A[l:i] और A[m:j] का sorted merge है। उसमें दोनों runs के k सबसे छोटे records हैं और equal-key order सुरक्षित है। शेष runs sorted होने से अगला minimum उनके heads में ही होगा। छोटा head चुनने से invariant बना रहता है। शुरू में prefixes खाली हैं। अंत में एक run खाली होता है; दूसरे का sorted suffix जोड़ना सही है।
Stable sort में equal-key records का मूल relative order बचता है। Recursive halves stable हों और tie पर left चुना जाए तो मूल left half के बराबर records right half वालों से पहले रहेंगे। Tie पर right लेने से numeric order सही होते हुए भी stability टूट सकती है।
हल किया merge: left [2a,5,7], right [2b,3,8]। Letters records की पहचान हैं। Comparisons से क्रमशः 2a,2b,3,5,7 चुने जाते हैं; 8 append होता है। Result [2a,2b,3,5,7,8], key comparisons पाँच और output moves छह हैं। Nonempty runs की lengths p,q हों तो अधिकतम p+q−1 comparisons चाहिए; एक खाली होने पर suffix के लिए comparison नहीं चाहिए।
3. Time और memory
सामान्य merge सभी n records process करता है। Powers of two पर T(n)=2T(n/2)+Θ(n), T(1)=Θ(1)। हर merge level का कुल work Θ(n), levels log2 n, इसलिए इस implementation में best और worst दोनों Θ(n log n) हैं। पहले से sorted input भी merge work नहीं हटाता, जब तक अलग early-exit optimization न जोड़ें। Unequal halves पर भी यही asymptotic bound है।
एक reusable n-record buffer लें और calls को उसके ranges दें: buffer Θ(n), recursive stack Θ(log n), कुल auxiliary space Θ(n)। पूरे execution में allocations का योग simultaneous memory नहीं है। यह array implementation O(1)-extra-memory अर्थ में in-place नहीं। Bottom-up merge sort recursion हटा सकता है, buffer फिर भी चाहिए। Linked-list variant की storage/movement अलग हो सकती है।
परीक्षा की गलतियाँ
Sorted output मात्र से stability सिद्ध नहीं होती। Split index pivot value नहीं है। Merge के input runs sorted होने चाहिए। Copy-back भी linear combine work में गिनें। p+q−1 worst-case bound है, हर input की exact संख्या नहीं।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. Stable merge में equal keys पर किसे चुनें?
A. Left run B. Right run C. हमेशा कोई भी D. कोई नहीं
उत्तर: A
A: Left से मूल cross-half order बचता है।
B: Right equal records उलट सकता है।
C: कोई भी चुनने से guarantee नहीं।
D: एक record चुनना होगा।
P02. 4 और 5 length के runs merge करने में अधिकतम key comparisons?
A. 4 B. 5 C. 8 D. 9
उत्तर: C
A: इतनी जल्दी run खाली जरूरी नहीं।
B: दोनों और देर तक nonempty रह सकते हैं।
C: 4+5−1=8।
D: अंतिम record को comparison नहीं चाहिए।
P03. बिना early-exit वाला array merge sort sorted input पर:
A. Θ(1) B. Θ(n) C. Θ(n log n) D. Θ(n²)
उत्तर: C
A: हर record process होता है।
B: Linear work वाले logarithmic levels हैं।
C: सभी merge levels चलते हैं।
D: Balanced split quadratic time रोकता है।
P04. Reusable buffer और recursive calls का कुल extra space?
A. Θ(1) B. Θ(log n) C. Θ(n) D. Θ(n log n)
उत्तर: C
A: Buffer constant नहीं।
B: यह केवल stack है।
C: Linear buffer stack से बड़ा है।
D: सभी levels के अलग n buffers साथ जरूरी नहीं।
P05. [1,4] और [2,3] merge में कितने key comparisons?
A. 1 B. 2 C. 3 D. 4
उत्तर: C
A: केवल 1 चुनेगा।
B: 2 के बाद 3 से भी compare होगा।
C: 1:2, 4:2, 4:3; फिर 4 append।
D: 4 append को comparison नहीं चाहिए।
P06. Merge शुरू होने से पहले क्या आवश्यक है?
A. सभी keys अलग B. दोनों runs sorted C. Left maximum right minimum से छोटा D. दोनों lengths समान
उत्तर: B
A: Duplicates स्वीकार हैं।
B: Sorted heads अगला global minimum देते हैं।
C: यह केवल आसान special case है।
D: असमान lengths भी merge होती हैं।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे Algorithms syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन