Does this time complexity for sorting match any known algorithm?

Asked Mar 05 '17 at 19:10

Active Dec 08 '19 at 18:39

Viewed 63 times

Have been tinkering with sorting algorithms for a while and think I have a new one - a n un stable in-place algorithm whose best and worst case comparison is same at 3^(k-1) + 2^(k-1) where n = 2^(k).

I thought I had two others - n log(n) log(n) and n*k but believe they are inplace-merge-sort and binary-quick-sort/binary-radix-sort respectively. However I've not so far encountered any with the above time complexity.

Update #2 :

Question is whether there is already any known stable, in-place sorting algorithm with a time complexity of 3^(k-1) + 2^(k-1) where n = 2^(k).

edited Dec 08 '19 at 18:39

SecretAgentMan

2,856
7
21
41

asked Mar 05 '17 at 19:10

Ravindra HV

2,558
1
17
26

I might have not get it 100%, what is the question? – Maytham Fahmi Mar 05 '17 at 19:19
Question is whether there is already any known stable, in-place sorting algorithm with a time complexity of `3^(k-1) + 2^(k-1)` where `n = 2^(k)`. – Ravindra HV Mar 05 '17 at 19:21
3

3^(k-1) ~ 3^k ~ 3^logn = n^log3 ~ n^1.584. Nah it's too slow. – tnt Mar 05 '17 at 19:28
Agreed. But given that its still better than n^2 so wanted to check any how. – Ravindra HV Mar 05 '17 at 19:31

Does this time complexity for sorting match any known algorithm?

0 Answers0