Как слить два уже отсортированных массива в третий массив БЕЗ использования алгоритма сортировки?

Question

допущения и ограничение:

• Есть два массива сортируется в порядке возрастания A [] и B [] различных размеров.

• Вы должны объединить их в третий массив c [] в порядке возрастания.

• Вы не можете объединить два массива, выполнив их в третьем массиве, а затем примените алгоритм сортировки для их сортировки.

• Вам не нужно использовать какой-либо алгоритм сортировки по всей задаче.

• Вы должны воспользоваться тем фактом, что [] и B [] уже отсортированы массивами, они могут меня слит без сортировки третьего массива с []

  SUGGESSIONS:

• это будет здорово, если бы вы могли добавить строки комментариев, чтобы сделать его легко понять, для начинающих

• язык кодирования для использования предпочтительно должен быть C. (я также хорошо с C++ и Java)

• Я не спрашиваю или не отвечаю на вопросы здесь, поэтому, пожалуйста, помогите мне быть более ясными, исправляя или улучшая свой язык.

Answer 1

Я предполагаю, что вы нашли пример here (просьба указать ссылку!), Но это немного сложнее. Я предпочитаю следующее:

// c[] MUST be pre-allocated to at least n_a+n_b 
void merge_sorted(int n_a, const int a[], int n_b, const int b[], int c[]) 
{ 
    int i = 0, j = 0, k = 0; 
    while (i < n_a && j < n_b) 
     if (a[i] < b[j]) c[k++] = a[i++]; 
     else c[k++] = b[j++]; 
    while (i < n_a) c[k++] = a[i++]; 
    while (j < n_b) c[k++] = b[j++]; 
} 

Он не проверяет, отсортирован ли вход.

EDIT: версия с выделением кучи внутри функции:

// the caller is responsible for calling free() on the returned pointer 
int *merge_sorted(int n_a, const int a[], int n_b, const int b[]) 
{ 
    int i = 0, j = 0, k = 0, *c; 
    c = (int*)malloc((n_a + n_b) * sizeof(int)); 
    while (i < n_a && j < n_b) 
     c[k++] = a[i] < b[j]? a[i++] : b[j++]; 
    while (i < n_a) c[k++] = a[i++]; 
    while (j < n_b) c[k++] = b[j++]; 
    return c; 
} 

Я обычно предпочитаю, чтобы звонящие управлять распределением кучи.