Last active
December 20, 2022 14:21
-
-
Save thanhnguyentang/12a2e634d5be5eb30f1a to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| MERGE(A,p,q,r) | |
| // Merges 2 sorted arrays into a single sorted array | |
| // where A[p..q] and A[q..r] are sorted subarrays. | |
| n1 = q - p + 1 | |
| n2 = r - q | |
| let L[1..n1+1], R[1..n2+1] be new arrays | |
| for i = 1 to n1 | |
| L[i] = A[p+i-1] | |
| for j = 1 to n2 | |
| R[j] = A[q+j] | |
| L[n1+1] = -infinity | |
| R[n2+1] = -infinity | |
| i = 1, j = 1 | |
| for k = p to r | |
| if L[i] <= R[j] | |
| A[k] = L[i] | |
| i = i+1 | |
| else | |
| A[k] = R[j] | |
| j = j+1 |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| MERGE-SORT(A,p,r) | |
| // merge-sort subarray A[p..r] | |
| if p < r | |
| mid = [(p+r)/2] | |
| MERGE-SORT(A,p,q) | |
| MERGE-SORT(A,q+1,r) | |
| MERGE(A,p,q,r) |
Author
Glad you found the answer :)
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
The best feeling is when you are formulating a precise question to write in comment to ask about the code in despair, and after finally formulating correct question, you realize and find the answer yourself🤤😂 (I was about to ask what the fudge are r, p,q??, While being confused about the meanings of A(q..r) and A[p...q]. The answer struck me after half an hour of going back and forth from this code to other tasks)