Sorted Array Merge Problem: Design an algorithm to merge two sorted positive integer arrays A and B. Size of array A is n and size of array B is m. Array A has m empty blocks(-1) at random places. Merge array B into A such that array A is sorted and does not have empty blocks.
The approach is simple and reminds me of my old tape handling days. Would be fun if someone describes the problem as two data tapes and see where the reader goes.
A good start would be to define test cases (Boundary cases)
- all of B occurs before any of A.
- all of B occurs after all of A
A simple routine would be to compact A so all of the empty blocks are at the front and then just walk both arrays, picking the smallest number from each array to fill in the resulting array.
Unit testing is simple:
Complexity is O(n) and no extra space is needed.