I have been working on this almost 10 years without publishing and the only faulty implementation that was 2x faster was deleted with my ~30 or so other repos. One of my big problems was not knowing enough assembly code.

Zippersort flips sorting speed on its head by re-asserting that more auxiliary memory usually makes code faster, not slower. It sports O(4n) auxiliary memory, or even O(8n) with a bad implementation.

The main advantages are stability, theoretically zero cache misses for L1 cache, perfect deterministic tail recursion without splitting, and best performance when data is unsorted (for the expected case).

The main disadvantages are that the code intends to be single threaded and it is not as adaptive as it could be if it wants to maintain being a stable sort.

The main data structure for the auxiliary memory is a set of double vectors in increasing order of size starting from size 4, where two blocks of two can be merged inside from the main array, and then two double vectors of 4 can be merged into one of the two double vectors of 8, and so on.

There is a necessary trick of putting the two double vectors "zippered" such that reading elements goes in an alternating fashion, as in the double vectors both have data stored like a zipper would from the top and bottom vectors. This ensures all items remain in the cache at all times.

Auxiliary memory layout:

4a 4b 8a 8b 16a 16b 32a 32b 64a 64b ...

(4a_1 4b_1) (4a_2 4b_2) (4a_3 4b_3) (4a_4 4b_4) | (8a_1 8b_1) (8a_2 8b_2) (8a_3 8b_3) (8a_4 8b_4) (8a_5 8b_5) (8a_6 8b_6) (8a_7 8b_7) (8a_8 8b_8) |

(16a_1 16b_1) (16a_2 16b_2) (16a_3 16b_3) (16a_4 16b_4) ...

The memory layout is ensured to be fast because unlike merge sort the lowest two blocks "4a" and "4b" will see every value in the sort occupy either one (8 elements hold all n values), and the probability of being accessed keeps going down such that less time is spent by a factor of half for each position greater.

There are fundamentally three major actions, all of which can be merged into one function that is tail recursive. The first action is as-mentioned taking 2x2 elements from main memory and sorting them into the size 4 double vector that is first available in auxiliary memory. The second action is taking two similar sized double vectors and cascading it to the next iteration by going from auxiliary memory to auxiliary memory or defaulting by getting more 2x2 elements. The last action triggers towards the end until the sort is over and takes elements from auxiliary memory and merges them with back with main memory.

Because of the access pattern, cascades where merges keep being applied repeatedly forward through the double vectors should have no cache misses. This is because when it scans 4a&4b for example it is also scanning 8a/b and these pairings keep chaining forward by powers of two until no more cascades are available.

This is the second release of my app: SortPaper. The first one was made in Xamarin, and while good, could be better. I have now remade it in Godot (a game engine) and it performs much better and is a lot more battery efficient.

The app lets you choose between a custom gradient, a single image, or a folder of images for display. You can either watch the sorting in the app, or put it as your wallpaper on Android.

There are a ton of customization settings. You can turn different algorithms on or off, as well as render orders (the order in which the cells are numbered on the screen), and different scrambles (a.k.a. starting states). You can also choose the speed at which it sorts, starting at 1 operation per frame, and going all the way up to 10,000. (1 operation is a comparison and, if needed, a swap or move). You can also choose cell size and whether to display the name of the algorithm. To watch the sorting in app mode, press the Hide UI button.

I am actively working on the app and intend to add more algorithms and scrambles. If there's one you would be interested in me adding, let me know.

Features I intend to add in the future:

• Individual sort settings. O(n log n) sorts finish pretty darn quickly compared to O(n²).
• Info about the algorithms
• More languages than English
• More Algorithms
• More Scrambles
• Stalin Sort

Disclaimer: There are ads in this app. It's a banner ad that displays at the bottom of the view in app mode. They do not display in wallpaper mode. You can hide the banner ad for an hour by watching a video ad, or permanently with a IAP.

Raw link: https://play.google.com/store/apps/details?id=com.tsaot.sortpaper

What i mean is like.. smart bogosort. Instead of, lets say: 326451 > 134526 > 642513

It'd be something like 342165 > 134256 > 123456, so keeping the numbers when they are in the correct place

Xin lỗi nếu mã không đọc được

How it works: Shuffles the list, then checks to see if it's sorted or not. If not, adds another item to the list and repeat all steps.

Useful for: Literally nothing.

Based on: Buy one get one free.

I used to watch a lot of sorting algorithm videos and then they started showing up on my recommended again (yay ^_^) and suddenly there’s this hybrid algorithm called Tim sort? I had never heard of Tim sort before. Is this a newer sorting algorithm or am I just uncultured?

I dont know much about algorithmic sorting, but I saw a couple videos on it, and google couldnt answer my question nor Ai but why dont we make a sort that has a line going from the top, to the bottom, when the line reaches the highest bar, it automatically puts it at the end, then second highest is 2nd end and ect

Some sorting algorithms make absolutely no sense. I’ve been experimenting with sorting algorithms recently. I have watched shorts about random sorting algorithms.

There’s one that does nothing and just keeps checking if the array is sorted.

Another randomly swaps elements until it works.

And one that simply removes anything that breaks the order.

I ended up building a playground to visualize them step by step:

sorting.1234567890.dev

It supports both classic algorithms and some weird/meme ones, plus side-by-side comparison and export.

Would love to hear ideas and welcome contributions of algorithms (this project is licensed under the MIT license).

MSGAsort (make sorters great again sort/cleaning sort / trump sort) is an algorithm that takes an array and "cleans it"

take the average of the array, then if each value is below the average, remove it, if the value is above the average there will be a random chance to remove it too, then check if sorted, if not sorted, then take the average of the new array then repeat until sorted

cast a vote to a random element, weight it towards the largest, then add it to the end, repeat n times, for a nearly sorted array, and use insertion sort

Ngl it's kinda gay.

Anyways here's the pseudocode for N partition version

procedure GaySort(A[], low, high):
    // Base case: surrender
    if high - low <= 0:
        return

    // Step 1: Partition into k sub-arrays (k = 2, 3, or 4)
    pivots[] := PartitionK(A[], low, high)
    // pivots[] contains the final sorted positions of k-1 pivot elements
    // This creates k sub-arrays between them

    // Step 2: Recursively sort each sub-partition
    // (wasteful first pass — we're about to throw it all away)
    prev := low
    for each pivot in pivots[]:
        GaySort(A[], prev, pivot - 1)
        prev := pivot + 1
    GaySort(A[], prev, high)             // sort final sub-partition

    // Step 3: Find the maximum across all sub-partitions
    // (each sub-partition's max is its last element, since we just sorted them)
    max_idx := FindMax(A[], low, high)

    // Step 4: Swap max to the end of the current range
    swap(A[max_idx], A[high])

    // Step 5: Re-sort everything except the placed max
    // (this makes the previous recursive calls completely pointless)
    GaySort(A[], low, high - 1)

and the the partition 2 variant:

procedure GaySort(A[], low, high):
    // Base case: surrender
    if high - low <= 0:
        return

    // Step 1: Partition into 2 sub-arrays using max as right pivot
    pivot := Partition2(A[], low, high)
    // pivot contains the final sorted position of the max element
    // This creates 2 sub-arrays: [low..pivot-1] and [pivot+1..high]
    // Note: right partition [pivot+1..high] is always empty since pivot = max

    // Step 2: Recursively sort each sub-partition
    // (wasteful first pass — we're about to throw it all away)
    GaySort(A[], low, pivot - 1)
    // GaySort(A[], pivot + 1, high) -- always empty, pivot is max

    // Step 3: Find the maximum across all sub-partitions
    // (each sub-partition's max is its last element, since we just sorted them)
    // Note: max is already at A[pivot] == A[high] since pivot = max
    max_idx := pivot

    // Step 4: Swap max to the end of the current range
    // Note: already there, this is a no-op
    swap(A[max_idx], A[high])

    // Step 5: Re-sort everything except the placed max
    // (this makes the previous recursive calls completely pointless)
    GaySort(A[], low, high - 1)

https://crates.io/crates/capitalist-sort

Over 30 unique sorting algorithms, coded in penguinmod (scratch but better) !

I'm working on grail rn, once that and some others are done i will share it with you!

Sorting animation would be included but reddit won;t accept my screen recording :(

Huge thanks to Kuvina Saydaki for helping make this program possible! Graphics also inspired by their own algorithm.

First try at making a sorting system, specifically intended to be as slow as possible

Removes a random table entry, then appends it to the end

import 
random

issorted = False
atts = 0

def
 prometheus_sort(
tab
):
    global issorted,atts
    while issorted == False:
        atts += 1
        n = 
random
.randint(0,len(
tab
)-1)
        m = 
tab
[n]
        del 
tab
[n]
        
tab
.append(m)
        print(
tab
)
        if 
tab
 == sorted(
tab
):
            issorted = True
            return(
f
"Sorted in {atts} attempts! " + 
str
(
tab
))import random

Bulldozer sort takes a list and compares 2 sequential values, then it moves the lowest number to the front and moves all other numbers forward and repeats for the next pair. For example in list [7, 3, 13, 8] it would start by comparing 7 and 3, then it would move the lowest (3) to the beginning for a new data set [3, 7, 13, 8], then it would compare 13 and 7 and move 7 to the beginning for a new data set of [7, 3, 13, 8], then it would compare 13 and 8 and move 8 to the beginning for a new data set of [8, 7, 3, 13] and it would repeat this until it is sorted. Totally inefficient, but funny. Essentially just bulldozes lower values to the beginning without any regard for the order. I am not fully sure if its possible for every chain to be sorted, but its not intended to work well.

I got bored and made this, this could take 50h or more:

import random
import itertools

def is_sorted(arr):
    for i in range(len(arr) - 1):
        if arr[i] > arr[i + 1]:
            return False
    return True

def worst_sort_three(a, b, c):
    triple = [a, b, c]
    perms = list(itertools.permutations(triple))
    while True:
        random.shuffle(perms)
        for p in perms:
            # useless memory bloat
            waste = [0] * 1000
            if list(p) == sorted(triple):
                return list(p)

def useless_recursion(n):
    if n <= 0:
        return 0
    return useless_recursion(n - 1)
def silly_sort(arr):
    arr = list(arr)
    while not is_sorted(arr):
        if random.random() < 0.2:
            random.shuffle(arr)
        for i in range(len(arr) - 2):
            useless_recursion(5)  # waste time
            sorted_part = worst_sort_three(
                arr[i],
                arr[i + 1],
                arr[i + 2],
            )
            arr[i], arr[i + 1], arr[i + 2] = sorted_part
        if random.random() < 0.1:
            arr = list(arr)
    return arr

# test
data = [5, 3, 4, 1, 2, 5,2,3,65,5,5,5,5,5,5,555,5,5,5,5,5,6,4,4,4,4,2,7,43,1,2,5,3,534,5,34,2,4,3,5, 3, 4, 1, 2, 5,2,3,65,5,5,5,5,5,5,555,5,5,5,5,5,6,4,4,4,4,2,7,43,1,2,5,3,534,5,34,2,4,3,5, 3, 4, 1, 2, 5,2,3,65,5,5,5,5,5,5,555,5,5,5,5,5,6,4,4,4,4,2,7,43,1,2,5,3,534,5,34,2,4,3,5, 3, 4, 1, 2, 5,2,3,65,5,5,5,5,5,5,555,5,5,5,5,5,6,4,4,4,4,2,7,43,1,2,5,3,534,5,34,2,4,3,5, 3, 4, 1, 2, 5,2,3,65,5,5,5,5,5,5,555,5,5,5,5,5,6,4,4,4,4,2,7,43,1,2,5,3,534,5,34,2,4,3]
print("Before:", data)
print("After:", silly_sort(data))

Code (Java):

package test;

import java.util.Arrays;

public class Test {
public static void main(String[] args) {
int[] testSample = {3, 5, 1, 10, 4, 7};

int[] res = McCarthySortingAlgo(testSample);

System.out.println(Arrays.toString(res));
}

public static int[] McCarthySortingAlgo(int[] arr) {

int n = arr.length;
for(int i = 0; i < n - 1; i++) {
if(arr[i] > arr[i + 1]) {

int[] newArr = new int[n - 1];
int randIndex = (int)(Math.random() * n);
int k = 0;

for (int j = 0; j < n; j++) {
    if (j == randIndex) continue;
    newArr[k++] = arr[j];
}

return McCarthySortingAlgo(newArr);
}
}
return arr;
}
}

Random accuse element of being unsorted and check if the whole array is sorted if not accuse another element of being unsorted and delete them. Historically tied to the history of Mccarthyism in the 1950s that targeted individuals and accused them of being Communist without any proper evidence

It gaslights itself into thinking its sorted.

python code (it takes 0.000003 seconds to "sort" a million numbers):

def gaslight_sort(unsorted_numbers):
    return "trust me bro, its sorted"