How to merge two already sorted arrays into a third array WITHOUT using a sorting algorithm?

Question

ASSUMPTIONS and LIMITATIONS:

There are two arrays sorted in ascending order a[] and b[] of different sizes.
You have to merge them into a third array c[] in ascending order.
You cannot merge the two arrays by coping them into the third array and then apply a sorting algorithm to sort them.
You do not have to use any sorting algorithm throughout the task.
You should take advantage of the fact that a[] and b[] are already sorted arrays, they can me merged without having to sort the third array c[]

SUGGESSIONS:
It will be great if you could add comment lines to make it easy to understand for beginners
The coding language to be used preferably should be C. (I'm also okay with C++ and Java)
I do not ask or answer questions here, so please help me be more clear by correcting or improving my language.

C or C++? They are not the same, and the solution can look differently in either language! — Aconcagua, Jul 24 '16 at 18:03
This is a task, not a question. Stackoverflow is not a coding service — Ohad Eytan, Jul 24 '16 at 18:04
what i guessed could work is assigning one array into the third array and then inserting each element of the second array into the third array one by one. this should be the logic, cant really think of a perfect code for it — Rawshn, Jul 24 '16 at 18:10
can you add some comments like m and n being size of a[] and b[] and why sorted[] you are sending as an argument , it is result you want right ??, than just make local variable in function mrge and return that sorted list from there — Vaibhav, Jul 24 '16 at 18:20
This is a standard [2-way merge](https://en.wikipedia.org/wiki/K-Way_Merge_Algorithms#2-Way_Merge), which is the "merge" portion of merge sort. — Jim Mischel, Jul 25 '16 at 15:24

user172818 · Accepted Answer · 2016-07-24T18:40:42.070

2

I guess you found the example here (please cite the link!), but that is a bit complicated. I prefer the following:

// 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++];
}

It does not check if the input is sorted, though.

EDIT: the version with a heap allocation inside the function:

// 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;
}

I usually prefer to let the caller manage heap allocations.

edited Jul 24 '16 at 18:40

answered Jul 24 '16 at 18:25

user172818

4,518
1
18
20

alright, I got it, but you preallocated c[] to the sum of sizes of the array. is it really impossible to do the merging without pre allocating? – Rawshn Jul 24 '16 at 18:36
[Don't cast `malloc()`](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc). – melpomene Jul 24 '16 at 18:45
@melpomene Thanks for the link, but I still prefer to cast it. I usually need to have my C code compiled with a C++ compiler, which will complain without the explicit cast. At the bottom line, casting is not an error. – user172818 Jul 24 '16 at 18:50
If you compile with a C++ compiler, it's not C code; it's C++. – melpomene Jul 24 '16 at 18:54
2

No, that is the intersection of C and C++. It is both valid C and C++ code. – user172818 Jul 24 '16 at 18:56

How to merge two already sorted arrays into a third array WITHOUT using a sorting algorithm?

1 Answers1