#include <iostream>

using namespace std;

int* mergeArrays(int a[], int m, int b[], int n)
{
    int *c = new int[m+n];
    int smaller;
    m > n ? smaller = m : smaller = n;
    int i = 0, j = 0, k = 0;

    while(i < smaller && j < smaller)
    {
        if(a[i] < b[i])
        {
            c[k++] = a[i++];
        }
        else
        {
            c[k++] = b[j++];
        }
    }

    while(i < m)
    {
        c[k++] = a[i++];
    }
    while(j < n)
    {
        c[k++] = b[j++];
    }
    /*for(int i = 0; i < k; i++)
        cout << c[i] << " ";*/
    return c;
}

void quickSort(int arr[], int left, int right) {

    int i = left, j = right;
    int tmp;
    int pivot = arr[(left + right) / 2];

    /* partition */
    while (i <= j)
    {

        while (arr[i] < pivot)
            i++;

        while (arr[j] > pivot)
            j--;

        if (i <= j)
        {
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
      }

      /* recursion */
      if (left < j)
            quickSort(arr, left, j);
      if (i < right)
            quickSort(arr, i, right);
}

int main()
{
    int a[4] = {4,3,2,1};
    int b[5] = {9,8,6,5,7};

    quickSort(a, 0, 3);
    quickSort(b, 0, 4);
    int *c = mergeArrays(a, 4, b, 5);

    cout << endl;
    for(int i = 0; i < 9; i++)
        cout << c[i] << " ";
    return 0;
}