Merge into extra capacity22.08
A has size n+m with the last m slots unused; B has m values. Merge from the right so you do not overwrite unread A values.
k writes from the end. Compare A[i] and B[j], place the larger at k, decrement. This is merge-sorted-array.
worked examples
Same skill, three traces. Read all three before you try it.
01from right - given
a = [1, 4, 0, 0],n = 2,b = [2, 8]- walk
k=3:4vs8→8k=2:4vs2→4k=1:1vs2→2k=0:1- result
[1, 2, 4, 8]
02left-to-right bug - given
a = [1, 4, 0, 0],n = 2,b = [2, 8], write small first intoa[0]- walk
overwrites
1before it is used- result
- lost data
03b leftover - given
a = [9, 0, 0],b = [1, 2]- walk
after placing
9at end, copy1,2into front- result
[1, 2, 9]
Write
Compare from the right and place the larger at
On
mergeInto(a, n, b, m).a has length n+m with a[n..] unused. b has length m. Both runs are sorted. k writes from the end.Compare from the right and place the larger at
k. Print the array if you merge left to right (overwriting unread a values), then the correct result.On
a=[1, 4, _, _] n=2 and b=[2, 8], correct is [1, 2, 4, 8].constraintsa has length n+m with a[n..] unused. b has length m. Both runs are sorted. n ≥ 1, m ≥ 1.
- Merge Sorted Array0/3 skills ready · arrays · easyopen
- Merge Sorted Array0/3 skills ready · arrays · easyopen
Every Check with Awel is frozen here. Open one to read the code or load it back into the editor.