What sorting algorithm has Worst-Case time-complexity of O(n!)

Question

I have looked all over the internet and cannot find such wc time-complexity sort algorithm.

And I believe it's not Bogo Sort since it's wc is not infinity

• Damien: A possible sorting algorithm is to generate all permutations of the input, and to check is the result is ordered. Worst case complexity O(n!). Even the bubble sort is much better! This seems to be Bogo sort?
• Damien: I just checked that Bogo sort consists is generating random permutations, so different than the enumeration sort of complexity O(n!)
• n. m. could be an AI: Every algorithm has O(n!) complexity, except those that are worse than that.
• superb rain: @NateEldredge Wikipedia says O((n+1)!).
• Surt: Bogo sort is unbound.

Answer 1

Such an algorithm could be Heap's algorithm, enriched with a verification after each swap that checks whether the array is sorted. Each modification to the array made by Heap's algorithm takes amortised O(1) time, so it has an overall time complexity of O(n!).

Add to that the verification to see that the array is sorted. If we do that naively, this would take a time complexity of O(n) each time it runs, making the overall time complexity O(n!n).

But we could first count the number of consecutive inversions (which could be a value between 0 and n-1). This step has a time complexity of O(n). In light of the greater time complexity of Heap's algorithm, this is irrelevant.

Then we could see how each swap in Heap's algorithm influences that count. There can be up to 4 consecutive pairs that are influenced by a swap, so it takes constant time to verify how the count is modified by the swap. If after the swap the count is zero, we know the array is sorted.

In the worst case Heap's algorithm has to go through all permutations before the count is found to be zero, so that represents a worst case time complexity of O(n!)

• Surt: That routine needs to be added to the table at en.wikipedia.org/wiki/Sorting_algorithm.