What is the average efficiency of this sorting algorithm?

Question

I was following down a rabbit hole of math when I came up with a sorting algorithm. I try looking around the internet to see if anyone has come up with the same thing. It doesn't seem like it was the case (if anyone can prove me wrong, please tell me). I think I will call it anti-bogosort. The sorting algorithm is a variation on bogosort but with a twist. Whenever you randomize the list, every item is in a different place than before.

Take the sorted list $\{1, 2, 3, 4, 5\}$. The randomization will require that every item is in a different location than it is now, so $\{2, 5, 3, 4, 1\}$ is not a valid randomization.

A key observation I noticed is that the list may only have the chance to become sorted if all items are in the wrong spot. If just one of them were to be correctly placed, it would not be able to be in the same spot again. This might change how different it is from normal bogosort. All I know for sure is that it is less efficient. This isn't my area of expertise, so if anyone could take a crack at it, be my guest.

Answer 1

I will show just that the algorithm works.

An order is just a permutation of the index order $\{1,\cdots,n\}$. Lets denote a permutation by $\sigma$, the set of all permutations of $n$ elements is called $S_n$.

Let $\sigma^*(i)=i~\forall i$ be the the permutation that represents the ordered list and let $\sigma_0$ be your initial permutation.

We want to know what happens if we iterate by randomly sorting derangements $$\sigma_i \in D = \{ \sigma\in S_n : \sigma(i) \neq i~\forall i=1,\cdots, n \}$$ and testing if $\sigma_i \circ \sigma_{i-1}\circ\cdots\circ \sigma_1 \circ \sigma_0 = \sigma^*$ or not.

This question here says that every $\sigma \in S_n$ is the product of two derangements. The classic bogosort is just a composition of several permutations, since we can construct any permutation by compositing two derangements, then, since bogosort works and $|S_n|=n!< \infty$, this version also works.

To show that both algorithms have the same complexity it is sufficient to show that uniformly taking $\sigma_i,\sigma_j \in D$, we have $$P(\sigma_i\circ\sigma_j = \sigma) \in O\left( \frac{1}{n!} \right)~\forall \sigma \in S_n,$$ because, that way, we can group the derangements two by two and they will work almost as if we allow any kind of permutation. I don't know if it holds, but it is easy to see that this probability is not uniform. Take $\sigma = \sigma^*$, the only way that $\sigma_j\circ \sigma_i = \sigma^*$ is if $\sigma_i = \sigma_j^{-1}$, therefore, $$ P(\sigma_i\circ \sigma_j = \sigma^*) = \frac{1}{|D|} > \frac{1}{|S_n|}, $$ since we are free to pick any $\sigma_i$, but after that $\sigma_j$ is defined.

I hope it was useful.