ToddlerSort

It occurred to me while watching my youngest attempt to stack a set of nesting blocks, that he might be on to something. After some careful algorithm design, I give you ToddlerSort, the bleeding (drooling?) edge of sorting algorithms:

public static List<T extends Comparable<? super T>>
        toddlerSort(List<T> list, double irritability)
        throws Tantrum {
    List<T> sorted = new ArrayList<T>(list);
    int i = 0;

    while (i < sorted.size() - 1) {
        if (sorted.get(i).compareTo(sorted.get(i+1)) > 0) {
            if (Math.random() < irritability) {
                throw new Tantrum();
            } else {
                Collections.shuffle(sorted);
                i = 0;
            }
        } else {
            i++;
        }
    }

    return sorted;
} 

This algorithm runs in O(∞) time, but in practice it is usually aborted before completion.