Merge two sorted arrays22.02
Sorted merge walks both arrays and always takes the smaller current element. Output is sorted. This is mergesort's combine step.
Compare a[i] and b[j], push the smaller, advance that pointer. After one array exhausts, append the rest of the other.
worked examples
Same skill, three traces. Read all three before you try it.
01interleave - given
a = [1, 4, 9],b = [1, 2, 8]- walk
1(a),1(b),2,4,8,9- result
[1, 1, 2, 4, 8, 9]
02all a then b - given
a = [1, 2],b = [8, 9]- walk
1,2then8,9- result
[1, 2, 8, 9]
03leftover a - given
a = [1, 4, 9],b = [2]- walk
1,2, then4,9- result
[1, 2, 4, 9]
Write
a and
Always take the smaller of
Merge
mergeSorted(a, b).a and
b are sorted non-decreasing arrays of integers. i indexes a. j indexes b.Always take the smaller of
a[i] and b[j]. Print the two current values before each take. After one array is used up, copy the rest of the other.Merge
[1, 4, 9] with [1, 2, 8] → [1, 1, 2, 4, 8, 9]. Also merge [1, 4, 9] with [2] → [1, 2, 4, 9].constraintsa and b are non-empty and sorted non-decreasing.
- 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.