Tech Qu: Merge two sorted arrays

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.

 

Code Snippet

1. public static int?[] MergeSorted(int?[] a, int?[] b)
2. {
3.   var ai = a.Length - 1;
4.   var bi = 0;
5.   var mi=0;
6.   // Move all nulls to end
7.   for(int i=a.Length-1; i > -1;i--)
8.     if(a[i] != null)
9.     {
10.       a[ai] = a[i];
11.       if(ai!=i)
12.         a[i] = null;
13.       ai--;          
14.     }
15.     //point to first non-empty one
16.   ai++;
17.   for(var i=0; i < a.Length; i++)
18.   {
19.     if (ai < a.Length && bi < b.Length)
20.     {
21.       if (a[ai] < b[bi])
22.       {
23.         a[i] = a[ai++];
24.       }
25.       else
26.       {
27.         a[i] = b[bi++];
28.       }
29.     }
30.     else
31.     if (bi < b.Length)
32.     {          
33.         a[i] = b[bi++];
34.     }
35.   }
36.   return a;
37. }

 

Unit testing is simple:

Code Snippet

1. int?[] a = {null, null, 1, 3,null,null};
2.       int?[] b = { 3,4,5,6};
3.       var result = Questions.MergeSorted(a, b);
4.       foreach(var i in result)
5.       {
6.         Console.WriteLine(i);
7.       }

 

Complexity is O(n) and no extra space is needed.