Implement the slowest possible sorting algorithm that retains a fast best case [closed]

Question

I have recently been on a quest to create really really slow sorting algorithms that make Bogosort seem like it is the best.

The task is simple: Sort an array of integers in as long average time as possible, with the average Bachmann–Landau notation begin as high as possible, while keeping the best case performance fast

The rules:

• Everything happening has to be productive in some sense. Using a slow function to generate numbers is not counted as productive (unless that is one of the faster ways to get those exact numbers, and your algorithm depends on them for some reason).
• Best case* time performace has to be \$o(2^n)\$ (i.e. faster than \$2^n\$).

*The fast best case is not allowed to be on already sorted data.

You need:

• Specify language
• The code / pseudocode
• An explanation + big O-notation for best and average case.

Scoring:

Scoring will be based in order of this list:

• Highest average big O-notation
• Being deterministic
• Fastest best case
• Working on sets that are not strictly totally ordered
• Earliest submission

For example, if two submissions have the same average runtime, but only one of them is deterministic, that one will win. If they are both either deterministic or non-deterministic, they are judged based on the fastest best case, and so on.

Example:

fastSort works by giving every item a randomly generated number, putting the lowest one first, then recursively sorting the rest based on those new values. If the resulting array is not sorted, then it loops until it is.

The random marking of card numbers have a \$\frac{1}{n!}\$ chance of being correct, so it will on average take \$n!\$ attempts to select the right numbers, and for each of these attempts, the method calls itself with 1 lower length. Thus the average time complexity becomes:

$$ \begin{align} T(n) &= n! \cdot T(n-1) \\ &= n! \cdot (n-1)! \cdot T(n-2) \\ &= n! \cdot (n-1)! \cdot (n-2)! \cdot ... \cdot 2! \cdot 1! \cdot T(0) \\ &= T(0) \cdot \prod_{k=1}^n n! := T(0) \cdot sf(n)) = \underline{O(sf(n))} \end{align} $$ \$\big[sf(x)\$ is the superfactorial\$\big]\$

The best case, excluding the case of already sorted data, is if the initial labeling is correct on every level down. This will cause the algorithm to go as many steps down as it takes to come to a part where the rest of the elements are already sorted, and then go back up again. The best of these cases is if only two elements have been swapped, in which case, it only goes 1 level down, and thus has a best case runtime of \$O(n)\$.

Looking at space efficiency: Every step down needs to store n-(#steps) numbers, so the maximum amount of numbers needed at any given time is: $$ \sum_{k=1}^n k = \frac{n^2+n}{2} = O(n^2) $$

Since the only time we compare the actual inputs, is in checking whether the array is sorted, means that it will work on any partially ordered set.

I have chosen to call it fastSort for obvious reasons. Here is a possible pseudocode-implementation (nothing language specific):

class Card<T>
{
    T value
    stack<int> cards
}

function fastSortHelper(cardArr: array<Card<T>>, offset: int)
{
    if (offset >= cardArr.length) then return

    while (cardArr is not sorted based on their top card)
    {
        push 1 random number to every cards stack
        find the element with the smallest top card, and swap it with the first.
        fastSortHelper(cardArr, offset + 1)
        pop the top number from every cards stack
    }
}

function fastSort (arr: array<T>, start: int, end: int)
{
    int length := end - start
    array<Card<T>> cardArr[length]
    initialize cardArr with the values from arr in [start, end), and an empty stack

    while (cardArr is not sorted based on their values)
    {
        push 1 random number to every cards stack
        find the element with the smallest top card, and swap it with the first.
        fastSortHelper(cardArr, 1)
        pop the top number from every cards stack
    }

    move the values from cardArr back into arr, in the correct range
}

Answer 1

Python 3, \$O\left(n^2\left(max\left(a\right)-min\left(a\right)+1\right)^{n-1}\right)\$

import itertools

def sort(a):
    m, n, l = min(a), max(a), len(a)
    for possible in itertools.product(range(m, n + 1), repeat=l):
        if (
            all(possible.count(i) == a.count(i) for i in possible) and 
            all(i <= j for i, j in zip(possible, possible[1:]))
        ):
            return list(possible)

Try it online!

When input only contains \$k\$ and \$k+1\$ each \$\frac{n}{2}\$ times. Its complexity is \$O\left(2^{\frac{n}{2}}\cdot n^2\right)\$.