CODE
/****************************************
** Solution by Siddhartha **
****************************************/
#include
#define ll long long int
#define fe(i, a, b) for (int i = a; i <= b; i++)
#define fl(i, a, b) for (int i = a; i < b; i++)
#define vc vector
#define mod 1000000007
#define el “\n”
#include <bits/stdc++.h>
using namespace std;

int nextgap(int gap)
{
if (gap <= 1)
return 0;
return (gap / 2) + (gap % 2);
}

void sol(int a[], int b[], int n, int m)
{
int gap = n + m;
int tot = n + m;
int i = 0, j = gap;
gap = nextgap(gap);
while (gap >= 1)
{
while (j < tot)
{
if (i >= n && j >= n)
{
int ti = i - n;
int tj = j - n;
if (b[ti] > b[tj])
swap(b[ti], b[tj]);
}
if (i < n && j < n)
{
if (a[i] > a[j])
swap(a[i], a[j]);
}
if (i < n && j >= n)
{
int tj = j - n;
if (a[i] > b[tj])
swap(a[i], b[tj]);
}
i++;
j++;
}
gap = nextgap(gap);
i = 0;
j = gap;
}
}

void solve()
{
int n, m;
cin >> n >> m;
int a[n], b[m];
fl(i, 0, n)
{
cin >> a[i];
}
fl(i, 0, m)
{
cin >> b[i];
}
sol(a, b, n, m);
fl(i, 0, n)
{
cout << a[i] << " ";
}
fl(i, 0, m)
{
cout << b[i] << " ";
}
}

int32_t main()
{

``````ios_base::sync_with_stdio(false);
cin.tie(NULL);

solve();

return 0;
``````

}
Test Case where it fails
25 14
2 6 7 8 9 9 10 10 11 12 12 12 12 13 13 13 14 15 16 16 17 18 18 19 20
1 5 5 7 7 8 9 11 15 18 18 18 20 20