Sorting large array of long long int

c-plus-plus
largeintegers
sorting

#1

Hey guys, i’m working on a problem where I have to sort large array of long long int ( array size of nearly 1000000). I’ve tried to do it with merge sort as it has a complexity of O(n*log(n)) in worst case but still getting TLE. So , is there’s a most efficient way (time speaking) to sort all this data ? thank you :slight_smile:


#2

i dont know why but qsort() didnt work for me when i tried to sort %lld, so i used sort(a, a+n) from <algorithm>


#3

Same thing. I tried a different version where I used a vector and the sort function from but still getting TLE :confused:


#4

Advice:
shortn your long integer to their decimals by dividing it to {100,1000 or 1000000}.

put them in new array , apply function “Sort” on the new array,
then arange your real ‘the long’ array according to the positions of the small array.

Note: this way is way successful with diffrent long Numbers array, but i don’t now for simlar big no. with least digits changes, for ex: 966662… 966661… 966663… 9666631…


#5

i dont know vectors. why dont you use maps, which automatically sorts


#6

I don’t get it. what do you mean by using maps ?