#!/usr/bin/python3
"""Is this optimized bubble sort really bubble sort?

<https://blog.reverberate.org/2020/05/29/hoares-rebuttal-bubble-sorts-comeback.html#fallback-for-sorting-short-arrays>

I thought it wasn’t, but I guess it is.

This is extremely interesting, and would still be interesting even if
it weren’t really bubble sort, because the claim is that, on
superscalar hardware with deep pipelines, this sort beats insertion
sort for small arrays because its branches are all very predictable
(assuming the min and max operations in the inner loop are not done
with branches) and its data dependency graph permits very high ILP.
Insertion sort, by contrast, has a inner loop whose terminating branch
is very unpredictable.

You’d think that insertion sort’s better locality of reference and
smaller number of comparisons would more than make up for this, but
that isn’t what Gerben Stavenga found.  His quicksort (falling back to
this bubble sort for short subarrays) was 6× as fast as qsort(), 3× as
fast as std::sort, and 2× as fast as Alexandrescu’s quicksort.

"""

def pseudobubble(arr, i):
    """Implements the inner loop of the alleged bubble-sort from that URL.

        auto max = arr[0];
        for (size_t j = 1; j < i; j++) {
          auto y = arr[j];
          arr[j - 1] = (max <= y ? max : y);
          max = (max <= y ? y : max);
        }
        arr[i - 1] = max;
    """
    max_ = arr[0]
    for j in range(1, i):
        y = arr[j]
        arr[j - 1] = min(max_, y)
        max_ = max(max_, y)

    arr[i - 1] = max_


def realbubble(arr, i):
    """Implements the inner loop of real bubble sort."""
    for j in range(1, i):
        if arr[j - 1] > arr[j]:
            arr[j - 1], arr[j] = arr[j], arr[j - 1]

def sukutrule():
    return [10, 4, 1, 0, 11, 3, 6, 2, 1, 9]

def show_difference():
    p = sukutrule()
    r = sukutrule()
    for i in range(len(p), 1, -1):
        pseudobubble(p, i)
        print('pseudobubble', p)
        realbubble(r, i)
        print('real bubbles', r)

if __name__ == '__main__':
    show_difference()