# Monk and Sorting Algorithm[HackerEarth]

Hello guys can you help me reduce the time complexity of my code for the problem Monk and Sorting Algorithm: https://www.hackerearth.com/practice/codemonk/

I tried to optimize my code as much as possible and now I have no idea to further reduce the time complexity.

``````**#include<bits/stdc++.h>**
``````

** #define ll long long int**

** using namespace std;**

** int counter;**

** bool anyNonZero = false;**

** ll powerOf10[19];**

** bool compare(const int& a, const int& b){**

** ll wa = a;**

** wa/=powerOf10[min(18, 5*(counter-1))];**

** wa%=powerOf10[min(18, 5counter - 5(counter-1))];**

** ll wb = b;**

** wb/=powerOf10[min(18, 5*(counter-1))];**

** wb%=powerOf10[min(18, 5counter - 5(counter-1))];**

** if(wa!=0 || wb!=0) anyNonZero=true;**

** return wa<wb;**

** }**

** void print(vector& num){**

** for(int i=0;i<num.size();i++){**

** cout << num[i] << " ";**

** }**

** cout << endl;**

** }**

** int main(){**

** int n;**

** cin >> n;**

** powerOf10[0]=1;**

** for(int i=1;i<=18;i++) powerOf10[i]=powerOf10[i-1]10;*

** vector num(n);**

** for(int i=0;i<n;i++) cin >> num[i];**

** counter = 1;**

** while(true){**

** anyNonZero = false;**

** stable_sort(num.begin(), num.end(), compare);**

** if(!anyNonZero) break;**

** print(num);**

** counter++;**

** }**

** return 0;**

** }**

I did nothing fancy, I kept finding the weight and then sorting the vector using the stable_sort function and then printing my result.

My time complexity as I think should be O(5*(time taken by stable sort)) which is when I googled to be O(5nlog^2n).

I have solved it in java. But the key reason why I was getting TLE was becuase I wasnâ€™t using fast Input Output. So, just search out the web for Fast Input and Output in C++, it surely will help you!

stable_sort of STL takes O(n*(logn)^2) space in case of memory insufficiency. Since here the numbers are large that might be the case. Hence we need to implement merge sort for the same.

``````#include <bits/stdc++.h>
using namespace std;

using ll = long long int;

ll arr[1000001], tmp[1000001], org[1000001], tmp1[1000001];

void merge(int start, int mid, int end)
{
int p = start;
int q = mid;
int r = p;
while (p < mid && q <= end) {
if (arr[p] <= arr[q]) {
tmp1[r] = org[p];
tmp[r++] = arr[p++];
} else {
tmp1[r] = org[q];
tmp[r++] = arr[q++];
}
}
while (p < mid) {
tmp1[r] = org[p];
tmp[r++] = arr[p++];
}
while (q <= end) {
tmp1[r] = org[q];
tmp[r++] = arr[q++];
}
for (p = start; p <= end; ++p) {
arr[p] = tmp[p];
org[p] = tmp1[p];
}
}

void merge_sort(int l, int r)
{
if (l < r) {
int mid = (l+r) >> 1;
merge_sort(l, mid);
merge_sort(mid+1, r);
merge(l, mid+1, r);
}
}

void solve(){

ll n;
scanf("%lld", &n);

ll max_ele = 0, multiplier = 1;

// we need to make chunks until there are no chunks left
// a good way to know this is make chunks of max ele of arr
for(int i = 0; i < n; i++){
scanf("%lld", &org[i]);
if(org[i] > max_ele) max_ele = org[i];
}

while(max_ele / multiplier){

for (int i = 0; i < n; ++i) {
arr[i] = (org[i] / multiplier) % 100000;
}

// Implementing merge sort O(nlogn)
merge_sort(0, n-1);

for(int i = 0; i < n; i++)
printf("%lld ",org[i]);
printf("\n");

multiplier *= 100000;
}
}

int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

solve();

return 0;
}
``````