Worst case sort time is actually O(n**2), not O(n * log(n))

[tanriol]

Counter-example:

    elif array_type == 'X-shaped':
        random_data = [abs(i - size // 2) * ((-1) ** i) for i in range(size)]

Benchmarking results for this example on my machine

--- X-shaped ---
Array Size |  Merciful Stalin (s) |  Merge Sort (s) |  Quick Sort (s) | Bubble Sort (s) | Insertion Sort (s)
------------------------------------------------------------------------------------------------------------
       100 |             0.000406 |        0.000162 |        0.000385 |        0.000512 |           0.000206
       500 |             0.008444 |        0.000899 |        0.011718 |        0.016313 |           0.006826
     1,000 |             0.042343 |        0.001878 |        0.046340 |        0.069664 |           0.027881
     2,000 |             0.151176 |        0.004479 |        0.192380 |        0.297812 |           0.119710
     5,000 |             0.968564 |        0.014908 |        1.235482 |        2.013621 |           0.799174
    10,000 |             3.840734 |        0.027826 |        4.871039 |        7.971764 |           3.138844
    20,000 |            15.662325 |        0.053856 |       19.865934 |       32.706325 |          13.008377

[tanriol]

Actually even the average case results for the random array according to your graphs look more like O(n ** (3/2)), not O(n * log(n))

[BBrixen]

@tanriol wonderful counterexample that you found. I thought I had one, but it turns out that mine was, in fact, not a counterexample. Props to @r-kataria 's algorithm for being fairly robust against constructed arrays. Most of the time, it was able to entirely "prune" half the array in 1 pass, since my failed counterexample was semi-sorted.

I looked a bit more in depth into the working counterexample, and the worst-case runtime is $O(n^2)$. Despite what the graphs look like, it is not $O(n^{3/2})$ (empirical results can only get you so far). Lets break it down with some minor theory :)

The original claim in the README of:

NB: It is impossible for an array to have all elements unordered in both the forward and backward passes simultaneously. This inherent design ensures that each pass successfully reduces the size of the unsorted portion of the array geometrically, preventing an O(n²) runtime and maintaining the algorithm's efficiency by ensuring progress is made at every recursive step.

is unfortunately untrue. The size of the subproblems in @tanriol 's X-shaped arrays do not decrease geometrically. That is, the merciful-stalin sorting algorithm is unable to reduce the problem to a fraction of its size. I printed the size of the array at the start of each call to merciful-stalin, and it decreases by 4.

Here is an example for an array of size 10. The remaining elements after the forward and backward passes are printed

[5, -4, 3, -2, 1, 0, 1, -2, 3, -4, 5]

new call. size: 10
forward remaining:
[-4, 3, -2, 1, 0, 1, -2, 3, -4]
backward remaining:
[3, -2, 1, 0, 1, -2, 3]

new call. size: 7
forward remaining:
[-2, 1, 0, 1, -2]
backward remaining:
[1, 0, 1]

new call. size: 3
forward remaining:
[0]
backward remaining:
[]

A slightly larger test of n=100 confirms that the array only decreases by 4 on each recursive call. In fact, any arbitrary n will show the same pattern.

100
97
93
89
85
81
... (this pattern repeats)
17
13
9
5
1

This is due to the fact that the algorithm is only able to prune off the first and last element for each forward and backward pass. Now that we know that (in the worst case) the size of the array decreases by a constant amount, the recurrence is simple to solve. For some constant $k$ (say, $k=4$ in our case), we get the recurrence

$$ T(n) = T(n - k) + O(n) = O(n^2) $$

I would still agree with you that the expected runtime is $O(n \cdot \log n)$. This is pending a proof of course

Unnecessary tangent:

A thought that occured to me is: what if we used the Longest Increasing Subsequence (LIS) to obtain the forward pass (and likewise for the backward pass). This takes $O(n \cdot \log n)$ time to find, but may give us guarantees about the size of subproblems.

Open question (both to myself or anyone reading):

1. What is the expected size of the LIS for a random array of size n?
2. What is the worst case size of the LIS for a random array of size n?
3. What is the worst case LIS for both the forward and subsequent backward pass of this algorithm on an array of size n?

Let us assume that LIS does give us a guaranteed fractional-sized subproblem. The recurrence would be of the form

$$ T(n) = T(n / k) + O(n \cdot \log n) = O(n \cdot \log n) $$

[tanriol]

@BBrixen, thanks, I've thought about that quite a bit.

I looked a bit more in depth into the working counterexample, and the worst-case runtime is $O ( n ^ 2 )$ . Despite what the graphs look like, it is not $O ( n ^ { 3 / 2 } )$ (empirical results can only get you so far).

For the counterexample (worst case) it's indeed $O ( n ^ 2 )$. The point here was that it looks like $O ( n ^ { 3 / 2 } )$ even in the average case.

2. What is the worst case size of the LIS for a random array of size n?

1, obviously, as it can turn out to be decreasing.

3. What is the worst case LIS for both the forward and subsequent backward pass of this algorithm on an array of size n?

$O(\sqrt{n})$, the counterexample looks like this: [1, 0.99, 1.99, 0.98, 1.98, 2.98, 0.97, 1.97, 2.97, 3.97, ...].

1. What is the expected size of the LIS for a random array of size n?

For this question I haven't verified the references, but the Wikipedia article on LIS states that

For inputs in which each permutation of the input is equally likely, the expected length of the longest increasing subsequence is approximately $2 \sqrt{n}$.

and that likely increases the average case complexity of the MSS (not really sure what the theoretic average case complexity will be).