CODEWITHSUNDEEP
calgorithmsortingtime-complexitymergesort
gann
gann

Reputation: 49

O notation and merging two already sorted arrays

I've been told to merge two already sorted arrays, of different sizes, A and B into an array, C in linear time.

By linear time, I understood that the time complexity of this algorithm has to be O(n). Later on, I was also told to perform sorting while merging the arrays.

One idea I had was to create an algorithm where you have two pointers in both arrays, pointing at the smallest element. The smallest element which is pointed at would go into the new array. When one array is exhausted, the remaining elements of the other array are copied into the new array.

Since I just started programming a few months ago, I have found this difficult to implement and hence I decided to perform Merge Sort (MS) since it's the most similar to the above-mentioned algorithm. However, I'm concerned with the time complexity of MS itself - O(nlogn)

However, given that the two arrays would be already sorted, would the time complexity for MS be reduced or will it remain the same?

Thanks in advance.

Upvotes: 1

Views: 1207

Answers (2)

0___________
0___________

Reputation: 67476

merge two already sorted arrays, of different sizes, A and B into an array, C in linear time.

int *mergeArrays(const int *array1, const int *array2, size_t size1, size_t size2, int asc)
{
    int *result = malloc((size1 + size2) * sizeof(*array1));
    size_t index1 = 0, index2 = 0;
    size_t i;


    for(i = 0; i < size1 + size2 && index1 < size1 && index2 < size2; i++)
    {   
        if(asc)
        {
            if(array1[index1] > array2[index2]) result[i] = array2[index2++];
            else result[i] = array1[index1++];
        }
        else
        {
            if(array1[index1] > array2[index2]) result[i] = array2[index2++];
            else result[i] = array1[index1++];
        }
    }
    if(index1 == size1) memcpy(result + i, array2 + index2, sizeof(result) * (size2 - index2));
    if(index2 == size2) memcpy(result + i, array1 + index1, sizeof(result) * (size1 - index1));
    return result;
}

https://godbolt.org/z/PY8Ysv319

int cmpfunc (const void * a, const void * b) {
   return ( *(int*)a - *(int*)b );
}

void sort(int *array, size_t size)
{
    qsort(array, size, sizeof(array[1]), cmpfunc);
}

int *mergeArrays(const int *array1, const int *array2, size_t size1, size_t size2, int asc)
{
    int *result = malloc((size1 + size2) * sizeof(*array1));
    size_t index1 = 0, index2 = 0;
    size_t i;


    for(i = 0; i < size1 + size2 && index1 < size1 && index2 < size2; i++)
    {   
        if(asc)
        {
            if(array1[index1] > array2[index2]) result[i] = array2[index2++];
            else result[i] = array1[index1++];
        }
        else
        {
            if(array1[index1] > array2[index2]) result[i] = array2[index2++];
            else result[i] = array1[index1++];
        }
    }
    if(index1 == size1) memcpy(result + i, array2 + index2, sizeof(result) * (size2 - index2));
    if(index2 == size2) memcpy(result + i, array1 + index1, sizeof(result) * (size1 - index1));
    return result;
}

int main(void)
{
    srand(time(NULL));
    size_t size1 = rand() % 20, size2 = rand() % 20;
    int *mergedArray;

    if(size1 < 5) size1 += 5;
    if(size2 < 5) size2 += 5;

    int array1[size1], array2[size2];

    for(size_t i = 0; i < size1; i++)
        array1[i] = rand();
    for(size_t i = 0; i < size2; i++) 
        array2[i] = rand();
    sort(array1, size1);
    sort(array2, size2);

    for(size_t i = 0; i < size1; i++)
        printf("array1[%2zu] = %d\n", i, array1[i]);
    for(size_t i = 0; i < size2; i++)
        printf("array2[%2zu] = %d\n", i, array2[i]);

    mergedArray = mergeArrays(array1, array2, size1, size2, 1);
    for(size_t i = 0; i < size2 + size1; i++)
        printf("result[%2zu] = %d\n", i, mergedArray[i]);
}

You need to add memory allocation checks, NULL pointer checks etc.

Upvotes: 1

chqrlie
chqrlie

Reputation: 144695

Your task is to implement the merge phase of the mergesort algorithm. mergesort has a complexity of O(N.log(N)) to sort the dataset, but each merge phase takes linear time proportional to the length of the merged set.

Here is pseudo code for this:

merge(array a, array b into array c)
    int i = 0, j = 0, k = 0;
    while (i < len(a) and j < len(b)) {
        if (a[i] <= b[j]) {
            c[k++] = a[i++];
        } else {
            c[k++] = b[j++];
        }
    }
    while (i < len(a)) {
        c[k++] = a[i++];
    }
    while (j < len(b)) {
        c[k++] = b[j++];
    }
}

The complexity is linear as each step in each of the loops copies an element into the c array, for a total of len(a) + len(b) steps.

Upvotes: 4

Related Questions