I’m trying to solve inversions count problem in q.
I think merge sort is not suitable here and I implemented this in O(n*n) way.
Here is the code,
inversion1:{[x] y:(1+til count x)#\:x; sum sum each y >' x}inversion2:{[x] len:count x;cnt:0; i:0; while [i<len;j:i+1;while[j<len;if[x[i]>x[j];cnt+:1];j+:1];i+:1]; cnt}
Then I tested these 2 functions with \ts command.
a:100?100\ts inversion1 a\ts inversion2 a
In inversion1, I used adverb, so the speed was fast but consumed plenty of space (a lot of temp sublist generated).
In inversion2, there’s no adverb, it’s only a violent in-place implementation, so space consumption was fine but when the size of list > 10000, the speed was unacceptable.
Is there any elegant way to solve inversion count problem or any suggestions to my code so I can get time and space acceptable?
Thanks.