Hi!

I was playing around with sorting algorithms and came up with this ideea

**Code**

I am wondering how many times this code goes through the while loop

Also if you think that variations of this code (like changing the order in which we go through the powers of 2) could work better please let me know.

Thanks!

Please don't do this:

Well from my testing your version is really slow even for $$$n = 10^6$$$, however, this modification seems to make it reasonably fast:

"Please don't do this: bool changes = 1" Can you explain why ?

Not readable code.

Keywords true and false are there for a reason

Thanks, it makes a lot of sense why it works better when we start from a larger number and devide it by 2.

I think it's something similar to Shellsort.

Thanks for pointing this out. Indeed, it is quite similar to Shellsort.

Do you intend to make a youtube video about it?

These days I am very busy, I have a lot of work to do...( ͡° ͜ʖ ͡°)

Hello BlueDiamond.

I tried finding out the time complexity of the sorting algorithm in a rather experimental way. Here's what I found.

## Assumptions

since it is a comparison-based sort, I'll count the number of comparisons

tested for

strictly decreasing sequencesonly`rng`

equalsrng## What I did next

sequencesI counted the total number of comparisons done by

`solve`

for each arrayprinted the

number of comparisonsfor each sequence along with thelength of the sequencesinto a`csv`

wrote a Python3 script to plot the

`csv`

## Findings

This is what the plot looks like.It seems that $$$O(N \log{N})$$$ is a reasonable asymptote.

## Codes

solver.cppscript.pyMakefileHope this helps. :)

You need to count number of comparisons, not number of swaps.

Thanks _overrated_! It was very stupid of me. I edited the answer accordingly. :)