Choose smaller current element22.04
The next output is min(a[i], b[j]) when both remain. Ties: pick A then B (stable with A as the left run) or the opposite. Pick a rule.
If you pick the larger, the output is not sorted. If you forget the tie rule, stability of mergesort breaks.
worked examples
Same skill, three traces. Read all three before you try it.
011 vs 1 pick a - given
a = [1, 4],b = [1, 2]- walk
take
a's1first- result
[1, 1, 2, 4]withA-first ties
024 vs 2 - given
a = [1, 4],b = [1, 2], current4and2- walk
take
2- result
badvances
03wrong pick - given
a = [1, 4],b = [1, 2], take4first- walk
4before2- result
- unsorted
Write
a and
Return which side to take. On a tie, pick a first. Then merge
Tie
nextTake(a, i, b, j).a and
b are sorted non-decreasing arrays. i is an index into a. j is an index into b.Return which side to take. On a tie, pick a first. Then merge
[1, 4] and [1, 2] and print each choice.Tie
1 vs 1 takes a. Next 4 vs 2 takes b.constraintsa and b are non-empty and sorted non-decreasing. i < n and j < m while both remain.
- 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.