Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

Analysis

We have described how to merge two sorted arrays into a third sorted array. For this problem, as A is assumed to have enough space, we are not allowed to create a third array.

We cannot start the merge from the beginning of the two arrays,

Given two sorted arrays or lists, how to merge them into a sorted array?

This is a fundamental problem as it is a common requirement to merge two sorted arrays into one sorted array. The algorithm of merging two sorted arrays is also the basics of the one of the most famous sort algorithms: merge sort.

Suppose there are two sorted arrays A and B, and we want to merge them into a third Array C.

We define three indexes a, b, c, which points to the beginning of the three arrays A, B,