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, ,...
