merge - Merging two sorted lists, one with additional 0s -

consider following problem:

we given 2 arrays a , b such a , b sorted except a has b.length additional 0s appended end. instance, a , b following:

a = [2, 4, 6, 7, 0, 0, 0] b = [1, 7, 9] 

our goal create 1 sorted list inserting each entry of b a in place. instance, running algorithm on above example leave

a = [1, 2, 4, 6, 7, 7, 9] 

is there clever way in better o(n^2) time? way think of insert each element of b a scanning linearly , performing appropriate number of shifts, leads o(n^2) solution.

some pseudo-code (sorta c-ish), assuming array indexing 0-based:

pa = + len(a) - 1; pc = pa;                     // last element in while (! *pa) --pa;          // find last non-zero entry in pb = b + len(b) - 1; while (pa >= a) && (pb >= b)     if *pa > *pb         *pc = *pa; --pa;     else         *pc = *pb; --pb;     --pc while (pb >= b)                 // still bits in b copy on     *pc = *pb; --pb; --pc; 

not tested, , written off top of head, should give idea... may not have termination , boundary conditions right.