Skip to content

Instantly share code, notes, and snippets.

@anisur3036
Created January 8, 2023 16:43
Show Gist options
  • Save anisur3036/b0d89ed13305a394e700e77019434cd4 to your computer and use it in GitHub Desktop.
Save anisur3036/b0d89ed13305a394e700e77019434cd4 to your computer and use it in GitHub Desktop.
Problem solving using mearge sort
/**
WAP that takes 2 sorted (in non-increasing order) integer arrays as input, then merges the two arrays into one array sorted in non-increasing order in O(n+m).
Sample input Sample output
4
5 3 2 1
5
7 6 3 2 1 7 6 5 3 3 2 2 1 1
5
6 4 3 2 1
3
6 4 0 6 6 4 4 3 2 1 0
**/
#include <bits/stdc++.h>
using namespace std;
vector<int> mergeSort(vector<int> a, vector<int> b, vector<int> c)
{
if(a.size() <= 1)
{
return a;
}
vector<int>sorted_a;
int idx1 = 0;
int idx2 = 0;
int size = a.size();
for(int i = 0; i < size; i++)
{
if(idx1 == b.size()) {
sorted_a.push_back(c[idx2]);
idx2++;
} else if(idx2 == c.size()) {
sorted_a.push_back(b[idx1]);
idx1++;
} else if(b[idx1] > c[idx2])
{
sorted_a.push_back(b[idx1]);
idx1++;
} else {
sorted_a.push_back(c[idx2]);
idx2++;
}
}
return sorted_a;
}
int main() {
int n;
cin >>n;
vector<int> b(n);
for(int i = 0; i< n; i++)
{
cin >>b[i];
}
int m;
cin >> m;
vector<int> c(m);
for(int i = 0; i< m; i++)
cin >> c[i];
vector<int> array(n+m);
vector<int> ans = mergeSort(array, b, c);
for(int i = 0; i < ans.size(); i++)
cout << ans[i] <<" ";
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment