Esoteric Sorting Algorithms

Sorting algorithms are a classical way to teach efficiency. As a result, they tend to be robotically efficient. Sometimes people may need a reminder that computers are still made by humans and humans have a sense of humor. As a human with a sense of humor, I decided to browse the web and see what sorts of interesting sorting algorithms exist. Let's explore the fun and creative sorting algorithms that exist:

Sorts That Actually Sort

Let's start off with some normal sorts where the list actually ends up sorted in the end. These are more interesting.

Bogosort

Bogosort is by far the most infamous sorting algorithm. It's probably the only sorting algorithm in this list that also gets mentioned in lessons on sorting. In fact, the name "bogosort" actually comes from the word "bogus" since this sort is complete nonsense. Bogosort takes a list, shuffles it, then checks if the list is sorted. If the list is sorted, it'll stop but if it isn't sorted, it'll shuffle it again. This gives bogosort an average runtime of of O(n!) and a worst case runtime of O(infinity) Bogosort is also called permutation sort since it goes and generates permutations of the list until it just happens to find the permutation that's in the right order or random sort because well, it's completely random. Another name is monkey sort, in reference to the infinite monkey theorem which says that an infinite number of monkeys that spend an infinite amount of time banging on a keyboard will eventually be able to rewrite all of Shakespeare's works. Given enough time, bogosort will eventually produce the correct sorted array.

Double Bogosort

Perform bogosort twice so you can compare the results and make sure it's correct, found here

Bogobogosort

There's a subcategory of bogosort which first bogosorts the first element of the list, then bogosorts the first two elements of the list, then the first three until eventually, it reaches the end and has to bogosort the entire list. This is bogosorts within bogosorts which is absolutely useless since a successful bogosort for a smaller list won't help bogosort the larger list. To make it even more inefficient, if the list is ever out of order, then bogobogosort will resort again starting from the first element.

Bozosort

Bozosort is named similarly to bogosort and works similarly to bogosort. Bozosort is slightly faster than bogosort. Bogosort shuffles the entire list but bozosort picks two random elements of the list to swap until the list is sorted. There's also wandersort which is like a more efficient version of bozosort. While bozosort will swap the two random elements it picks no matter what, wandersort will choose two random elements but only swap them if they need to be swapped.

Miracle Sort

The previous sorts seem like they require some sort of miracle to function. Miracle sort needs even more of a miracle to function. Miracle sort checks to see if the list is sorted, if not, then it waits for a bit and after a bit, it'll check to see if the list is sorted again. The only way for miracle sort to sort an unsorted array is if by some miracle the bits in the computer were to somehow rearrange themselves in a way so that the list is sorted. Here is a Python implementation of miracle sort:

def miracle_sort(arr: list) -> list:
    """
    implementation of micracle sort

    Args:
        arr (list): the list to be sorted

    Returns:
        list: the finally sorted list
    """
    is_sorted = True
    for i in range(arr - 1):
        if not(arr[i] < arr[i + 1]):
            is_sorted = False
    if is_sorted:
        return arr
    else:
        return miracle_sort(arr)

I will argue that miracle sort actually will sort the list correctly, eventually, given some sort of miracle.

Quantum Bogosort

Quantum bogosort is actually another variation of bogosort but it's an interesting one. Quantum bogosort relies on the multiverse theory. Essentially how quantum bogosort would work is it would create a new universe for each possible permutation of the bogosorted list to exist. In each universe, the list would be checked. Any universe where the list isn't properly sorted is destroyed immediately. Please note that quantum bogosort is still completely hypothetical and no otherworldly inhabitants have been harmed in the testing of quantum bogosort yet. This image is a demonstration of how quantum bogosort would work: first it creates a new universe for each possible permutation of the list, then if the list isn't correctly sorted the universe is destroyed. In the end, the only universe that should remain is the universe with a correctly sorted list. This method poses no consequences as the inhabitants of the universes with incorrect permutations of the list wouldn't know they were destroyed after being destroyed. The positive side to quantum bogosort is an algorithm with a time complexity of O(1) and absolutely no barriers whatsoever in our current state of technology.

Worstsort

Worstsort also generates permutations. What worst sort does is to first generate all possible permutations, then it'll sort the possible permutations of the permutations so that it can find the correctly sorted one. Worstsort will use worstsort recursively to generate the possible permutations of the list. If worstsort keeps using worstsort to sort permutations of permutations so that it can find the correct permutation of the list it wants to sort, it would actually infinitely generate more and more permutations and never be sorted. As a result, when defining worstsort, there's also a depth defined. The depth is the maximum number of times to run worstsort before resorting to some other sort like bubble sort to sort the permutation of permutations of permutations. Worstsort's paper can be found here. Worstsort was inspired by other algorithms in a no longer existent internet thread called badsort. Badsort 2 seems to contain the same information though.

Stooge Sort

If there are two elements in the list, stooge sort will swap them if they aren't in the right order, otherwise nothing happens. Stooge sort for lists with a size of three or more work by first sorting the first 2/3 of the list, then sort the final 2/3 of the list then go back to sorting the first 2/3 of the list and continue repeating the process until the list is sorted. Each time it sorts some part of the list, it uses stooge sort recursively. Here is a visualization for stooge sort created using The Sound of Sorting

Sleep Sort

Sleep sort is actually a pretty smart idea if you think about it. It was originally posted on 4chan and can now be found in archives. Sleep sort takes advantage of multithreading). For each element in the list, sleep sort will let the element sleep for that many seconds, then print it. For example, let's say we have a list [4, 1, 9, 7]. Sleep sort would give each of the elements in the list its own thread where it would wait for that many seconds before printing itself. That means it'll first give 4 a thread where it would wait for four seconds then print 4, it'll give 1 a thread where it will wait one second and print 1, 9 gets a thread where it'll wait nine seconds before printing 9 and 7 gets a thread where it'll wait for seven seconds before printing 7. Assuming each new line is its own separate thread, each block represents one unit of time, sleep sort would make each element in the list sleep for that long before printing it. Sleep sort does actually work in theory but in practice, the threads could have slight differences and not necessarily print things in the right order. Fixing this would require either synchronization which would defeat the entire purpose of sleep sort or a longer delay time which means more sleep.

Exclusion Sort

Exclusion sort's first mention is on Twitter. This excludes an element, sorts everything else, then puts the element it took out back where it was before. Exclusion sort does this until the entire list is sorted. The only way for the entire list to be sorted is if the element taken out just happens to be in the correct spot already so exclusion sort also has a O(infinity) worst case run time.

Sorts That Don't Always Sort Correctly

There's also several sorting algorithms that don't always give the expected output of a normally sorted list. These are more fun.

Divine Sort

Divine sort is completely based on faith. We assume the list is sorted and ignore any evidence suggesting otherwise. Because of this, divine sort is the quickest sorting algorithm. Here is a Python implementation of divine sort:

def divine_sort(arr: list) -> list:
    """
    implementation of the divine sort algorithm

    Args:
        arr (list): the list given that needs to be sorted

    Returns:
        list: the clearly sorted list, don't say otherwise
    """
    return list

The first mention of divine sort seems to be this Reddit comment in a thread for bad sorting algorithms. A more well known version of divine sort is intelligent design sort which assumes the list is already sorted because whoever wrote it designed it intelligently.

Stalin Sort

This sorting algorithm is also called dictator sort and trump sort. Stalin sort runs in O(n) time. This sorting algorithm iterates through the list and removes any element that isn't in the right order for the list until the only elements that remain are sorted. Here's a fun visualized version of the sort. There's also a Github repository that implements the sorting algorithm in various different programming languages and has a much better explanation for the algorithm. Another name for this concept is dropsort. Another fun sort that deletes list elements is thanos sort which randomly deletes half of the list until the list ends up being sorted.

Stack Sort

This sort has absolutely nothing to do with stacks. How it works is it scrapes StackOverflow for posts tagged "sort" and "javascript". Stack sort can be tried here.

Hitchhiker's Sort

Replace the array with 42. Here's a python implementation:

def hitchhikers_sort(arr: list) -> int:
    return 42

Conway Sort

Here's an O(1) "sorting" algorithm that replaces the list with some random other list. Note the list it returns does not need to be sorted. Here's an example of a Conway sort implementation:

def conway_sort(arr: list) -> return list:
    """
    Conway sort implementation

    Args:
        arr (list): the list to be sorted

    Returns:
        return list: some static but arbitrary list
    """
    return [4, 43, 2346, 1, 8734765, 54]

Note that this isn't the only correct way to implement conway sort; there are an infinite number of random lists to hardcode.

Algorithmic Design Paradigms

There's a lot of sorting algorithms that actually sort which follow some sort of algorithmic design paradigm so rather than mentioning the sorting algorithms, I decided to mention the paradigm instead.

Multiply and Surrender

There's divide and conquer where the program divides the problem into two or more smaller subproblem and keeps dividing the subproblems too until the case is easy enough to be conquered on its own. Then, there's multiply and surrender which takes a problem, creates subproblems of the problem that are slightly simpler than the original problem and continues multiplying the number of subproblems there are until the subproblems are so simple that procrastination on finding the solution can no longer continue and the program has to surrender. An example of the difference between divide and conquer vs multiply and surrender would be the difference between quicksort and slowsort.

Conclusion

While it definitely is good to find good and efficient sorting algorithms, purposefully seeing how bad or how unrealistic an algorithm could be is certainly entertaining. A lot of concepts also go by different names so I'm sorry if I missed any algorithm names. Let me know in the comments if I missed any interesting sorting concepts!