FREDYSORT

How it works

1. Start with the first number in a new "sorted pile".
2. Pick a random number from the remaining unsorted pile -- this is the Fredy twist.
3. Use binary search on the sorted pile to find where it belongs -- cut the pile in half, check the middle, repeat until the exact spot is found.
4. Insert it there. Shift everything else to make room.
5. Repeat until the unsorted pile is empty.

Complexity

Python code

import random

def fredy_sort(arr):
    arr = arr.copy()
    unsorted = arr[1:]
    sorted_part = [arr[0]]

    while unsorted:
        # pick a random element
        rand_idx = random.randint(0, len(unsorted) - 1)
        current = unsorted.pop(rand_idx)

        # binary search for the right spot
        lo, hi = 0, len(sorted_part)
        while lo < hi:
            mid = (lo + hi) // 2
            if sorted_part[mid] < current:
                lo = mid + 1
            else:
                hi = mid

        # insert it
        sorted_part.insert(lo, current)

    return sorted_part