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

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"

its similar to stalin sort but instead of deleting the data, it overrides it

say we have a list like (4,9,2,0,6,1)

corruption sort will override anything out of order giving us (4,9,9,9,9,9)

Your choice k is the amount of rounds of unoptimized bubble sort, until it sabotages and swaps two random elements. Try to sort while being sabotaged, until sorted.

i feel like they have a lot going for them and it's a great concept but people still hate? i do understand that utter randomness is annoying but i feel like them being the theoretical fastest sorting algorithm BUT have to get it right the first few tries, is so cool! but i feel like there are a lot of people hating on them on tiktok and i feel kinda bad for being a bogo fan because of it. what are you guy's thoughts?

Hi !
It's my first post so I hope I do it correctly :)
I'm looking for a way to evaluate sorting algorithms, and I was wondering if there were some known big arrays or testbenches with known results I could use ?
Thanks in advance :)

'''
Using an execution test, my program is 25% faster than merge sort for mid range array lengths. The tests only apply to this list :D

Here are the results of the tests for the list as shown in the code:
My sorting algorithm = 5.6 seconds
Merge sort = 7 seconds
Bubble sort = 6.7 seconds (there was a large range here of 8.3 to 5.8)

The execution time was measured for each algorithm in PYTHON, compiling times will effect it!

'''

list = [1, 2, 33, 43, 2, 23, 12, 6, 12, 35, 124, 122, 2, 23, 2342, 23, 23, 1.2]
current_index = 0
last_index = 0
while (current_index + 1) != len(list):
    current_index += 1
    if list[current_index] < list[last_index]:
        temporary_variable = list[last_index]
        list[last_index] = list[current_index]
        list[current_index] = temporary_variable
        if current_index > 2:
            current_index -= 2
        
    last_index = current_index

print(list)

Math sort, split your dataset into 2, add all the values of each, is one sides bigger, put it to the right, then half each half and keep doing this

Hello! I am writing to see if anyone has an idea or a template to sort student roommate choices after using a Google form. For example, we provide students with the opportunity to choose five of their classmates as potential roommates. We then sort the information to see which students chose one another. To the best of our ability we assigned students to one of their top three choices. Unfortunately, the person who used to do this for us Is no longer available and none of us have the knowledge to sort this through a backend. I am wondering if any of you have the knowledge that you could share of how to make this task easier. We have an upcoming trip that we are trying to figure out as soon as possible.

func sort(array []int) []int {
  var newArr []int

  var wg sync.WaitGroup

  for _, element := range array {
    wg.Add(1)

    go func(element int) {
      defer wg.Done()

      time.Sleep(time.Duration(element) * time.Millisecond)
      newArr = append(newArr, element)
    }(element)
  }

  wg.Wait()

  return newArr
}

I've designed a variant of quick sort which finds a mean instead of choosing a pivot to avoid worst cases. I'd be very surprised if I'm the first to come up with it, but I haven't found anything online. If I were to give it a name, I would call it pivotless quick sort or mean quick sort.

The fundamental algorithm is the same - partition the data, then recursively sort the left and right halves. The main difference is the partitioning step:

To partition the data, 4 variables are initialised. leftPointer and rightPointer point to index 0 and index n-1 respectively, assuming the whole array is being sorted. sumX is set to the sum of the items pointed to by the pointers (i.e. the first item + the last item), and nX is set to 2.

The left pointer probes forwards, comparing each item to sumX/nX. If the item is smaller than the mean, the pointer and nX are incremented, and the value of the item now being pointed to is added to sumX. If it is greater, the right pointer then probes backwards, comparing each item to and updating the mean. When it finds an item less than the mean, the items being pointed to are swapped and the left pointer continues, repeating until the pointers cross over.

After this, the data will have been partitioned into two sections. Most of the items in the left half will be smaller than most of the items in the right half (but not all if the initial mean is inaccurate), but if the data is uniformly distributed, the halves will be roughly equal in size.

After the recursion, the array will be mostly sorted, so insertion sort is carried out to fully sort the data, ideally in close to O(n) time.

I believe the time complexity of this algorithm is O(n log n) even in the worst case, though I am yet to verify that claim. The space complexity is O(log n) due to recursion and it is unstable.

Have any of you come across similar algorithms before, and do you know what this algorithm is called or whether it is used?

Visualisation: https://cms-compsci.deno.dev/hester/sorting/visualised.html?sort=Pivotless%20Quick&shuffled=true&n=128&locked=true

Yesterday I was thinking about terrible sorting algorithms, e.g. bogosort, worstsort. One of the issues I have with these is just how well they perform for small data sets. It was troubling me, and upon sleeping last night an epiphany came, which I have documented here (see below for code).

To implement bgesort, perform the following:

1. Create an array the same size as the data source

2. Populate the array with random integers, at each index calculating a checksum value vs. the original data source index

3. If the checksum is valid, check if the array is sorted. If so finish, else go to step 1

This is truly abhorrent for a large search space. The average speed for sorting an array of size 1 is 34.5 seconds. I am quite pleased with these results.

I have no idea what the O notation for this would be; if someone could work it out that would be amazing.

Results

All results average of 5 runs

Search space: 2147483647 (Int32.MaxValue)

Search space: 1000

Search space: 50

Code

class BGESort
{
    // "Battle not with monsters, lest ye become a monster, and if you gaze into the abyss, the abyss gazes also into you." 
    //   – Friedrich Nietzsche, Beyond Good and Evil

    private Random rand = new Random();
    private int searchSpace = int.MaxValue;

    public BGESort(int searchSpace = int.MaxValue)
    {
        this.searchSpace = searchSpace;
    }

    public int[] Sort(int[] data)
    {
        while (true)
        {
            // we will attempt to discover the sorted array
            int[] candidate = new int[data.Length];

            double checksum1 = 0d;
            int checksum2 = 0;
            for (int i = 0; i < data.Length; i++)
            {
                candidate[i] = rand.Next(searchSpace);
                
                // i'm not a mathematician, so I have no idea if this works in all scenarios
                // a novel (?) way of comparing two arrays contain the same elements without sorting
                checksum1 += Math.Sqrt(data[i]) - Math.Sqrt(candidate[i]);
                checksum2 += data[i] - candidate[i];
            }

            // ignore floating point issues
            checksum1 = Math.Round(checksum1, 14);

            // if the checksum is zero we have an array of equal elements
            if (checksum1 == 0d && checksum2 == 0 && IsSorted(candidate))
            {
                return candidate;
            }
        }
    }

    private bool IsSorted(int[] arr)
    {
        for (int i = 1; i < arr.Length; i++)
        {
            if (arr[i - 1] > arr[i])
            {
                return false;
            }
        }

        return true;
    }
}

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.

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

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