Merge two sorted arrays

Challenge

Merge two already-sorted arrays into one sorted array.

Task

Implement void merge_sorted(const int *a, size_t na, const int *b, size_t nb, int *out) that merges the two sorted input arrays into out so that out holds all na+nb values in non-decreasing order.

Input

• a: sorted array of na ints (read-only).
• b: sorted array of nb ints (read-only).
• out: writable array with room for na+nb ints.

Output

Nothing returned; out[0..na+nb-1] contains the merged, sorted sequence.

Example

a={1,3,5}, b={2,4,6}   ->   out={1,2,3,4,5,6}
a={1,2,3}, b={}        ->   out={1,2,3}

Edge cases

• Either input may be empty (size 0).
• Equal values from both sides are both copied.

Input format

a (na sorted ints), b (nb sorted ints), out (room for na+nb ints).

Output format

Nothing returned; out holds all values merged in non-decreasing order.

Constraints

Both inputs are sorted; merge in O(na+nb).

Starter code

#include <stddef.h>
void merge_sorted(const int *a, size_t na, const int *b, size_t nb, int *out) { /* TODO */ }