In place merge sort 2 sorted arrays

Given two sorted arrays A and B of size (m+n) and m respectively, design an algorithm to merge A and B in-place.

e.g.  A = {8, 12, 15, 20, 22, 0, 0, 0, 0}
        B = {6, 13, 18, 19}
 Result= {6, 8, 12, 13, 15, 18, 19, 20, 22}

Approach
Apply 2-way merge. Advantage of this method is - it can be extended for any number of arrays (k-way merge). Take the last elements of arrays (22 and 19), put the highest element to the end of Array A. Next take 20 and the previous smaller element (19). Compare and put 20 in the last but one position. so on..

Solution

Sort array of 0,1,2

Given an array of 0s, 1s and 2s only in a mixed fashion. The task is to seperate out them such that 0s are on the left, 1s in the middle, and 2s on the right. The algorithm should run in linear time.

This problem is called "Dutch National Flag". There are lot of puzzles asked in the interview based on this.

Solution