Merging Two Sorted Lists Example: A[1..7]=5811481012 p=1,q=3,=7 4[1...3]and A[4...7]are already sorted nondecreasingly, please sort A nondecreasingly?How many comparisons do you need to give the answer?
Merging Two Sorted Lists Example: A[1…7]=5 8 11 4 8 10 12 p=1, q=3, r=7 A[1…3] and A[4…7] are already sorted nondecreasingly, please sort A nondecreasingly? How many comparisons do you need to give the answer?
Merging Two Sorted Lists Inputs:(1)A[1...m];(2)p,g,and r,and 1≤psq<Km,such that both Ap..g]and Ag+1..月 are sorted individually in nondecreasing order; Output:A[p...contains the result of merging the two subarrays A[p...g]and Ag+1...];
Merging Two Sorted Lists ◼ Inputs: (1) A[1…m]; (2) p, q, and r, and 1pq<rm, such that both A[p…q] and A[q+1…r] are sorted individually in nondecreasing order; ◼ Output: A[p…r] contains the result of merging the two subarrays A[p…q] and A[q+1…r];
Merging Two Sorted Lists 1.S-p,tk-q外1；k-P; 2.while sg and tr 3. if A[s]d then 4. 瓦←-ALS]; 5. s-s+1; 6. else ◆ 7. 氏←-AL; 8. t-t+1i 9. end if; ■ 10. k-k+1; ■ 11. end while; 12.ifS=qt1then瓦k.←-At..月 13.else瓦k..←-As.q] ■ 14.end if ■15.ALp.月←-p.月
Merging Two Sorted Lists ◼ 1. sp; tq+1; kp; ◼ 2. while sq and tr ◼ 3. if A[s]A[t] then ◼ 4. B[k]A[s]; ◼ 5. ss+1; ◼ 6. else ◼ 7. B[k]A[t]; ◼ 8. tt+1; ◼ 9. end if; ◼ 10. kk+1; ◼ 11. end while; ◼ 12. if s=q+1 then B[k…r]A[t…r] ◼ 13. else B[k…r]A[s…q] ◼ 14. end if ◼ 15. A[p…r]B[p…r]
Merging Two Sorted Lists What's the performance of the algorithm Merging Two Sorted Lists? v What's the minimum number of comparisons we need and in which case it will happen? vWhat's the maximum number of comparisons we need and in which case it will happen? vWhat's the minimum number of element assignments we need and in which case it will happen? vWhat's the maximum number of element assignments we need and in which case it will happen?
Merging Two Sorted Lists ◼ What’s the performance of the algorithm Merging Two Sorted Lists? ✓ What’s the minimum number of comparisons we need and in which case it will happen? ✓ What’s the maximum number of comparisons we need and in which case it will happen? ✓ What’s the minimum number of element assignments we need and in which case it will happen? ✓ What’s the maximum number of element assignments we need and in which case it will happen?
Merging Two Sorted Lists The number of element comparisons performed by Algorithm MERGE to merge two nonempty arrays of sizes n and n,respectively,where nsm,into one sorted array of size nm+is between n and n-1
Merging Two Sorted Lists ◼ The number of element comparisons performed by Algorithm MERGE to merge two nonempty arrays of sizes n1 and n2 , respectively, where n1n2 , into one sorted array of size n=n1+n2 is between n1 and n-1