Merge Two Sorted Arrays

Problem

Merge two given sorted integer array A and B into a new sorted integer array.

Example

A = [1,2,3,4]

B = [2,4,5,6]

return [1,2,2,3,4,4,5,6]

Solution

A very easy problem. A good practice to get familiar with arrays in your chosen language.

First create an array C of the size A.length + B.length.

Since A and B are already sorted, we simply choose the smaller one of the heads of the remaining A or B and add it to C. Make sure you can handle the cases where one array is exhausted, and the rest of the other array should all be added to C.

Language Specific Notes

• In Go, you cannot create an array with a variable, so make a slice instead. c := make([]int, lenA+lenB)
• In some languages, array length is a constant, while in others it is a function, which can be costly to calculate if you need it in each iteration.
• In some languages, i++ is allowed (e.g. Java, C++), so you can read the value and move the index at the same time, like C[k] = B[j++]; in other languages that is not allowed (e.g. Go).