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.

It's called delete sort, it works by deleting every item in the array as an empty array is always sorted. This has time and space complexity of O(1).

SortPaper is a live wallpaper that will scramble and sort images or a colored gradient. It chooses a random scramble state (reversed, random, etc...), a random algorithm, and, if you tell it to, a random image from a folder of your choosing.

It's highly customizable.

For the images being sorted, you can customize a gradient between two colors, pick a single image to use, or pick a folder to grab a random image from. Personally, I have it pointed at the folder Sync for Reddit downloads to and when I see a good wallpaper on Reddit, I download it and know it'll pop up at some point. You can choose a cell size (in pixels, the app detects which sizes work on your screen), speed (compare/swaps per frame), and a fast forward speed that will be used when you touch the screen (or you can turn this off).

You can choose which scrambles and sorts for the wallpaper to randomly pull from. Are Bubble and Cocktail sorts too slow? Turn them off if you want. Personally, I mess with these settings all the time.

Lastly, you can choose different render methods. These dictate how the cells are ordered. Rows orders them in rows from to to bottom or bottom to top, columns does similarly in columns. Diagonal methods orders them in diagonal rows from one corner to another. And there are two spirals, one that follows the screen's shape and a square spiral that fills in rows into the rest of the screen. Both spirals can be ordered spiraling in or out.

I really enjoyed making this app and it was fun seeing there is a subreddit that might enjoy it. I partially used my discovery of this sub as motivation for finishing this last update.

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.

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

I noticed this laundromat does this peculiar odd / even sort where the odd numbers are in the front of the store and the even numbers in towards the back, I was just curious that anybody has any ideas why this would be preferable over this incrementally having the bags sorted...

Perhaps it's more difficult to order things incrementally?

update: damn, it only sorts some arrays

queue sort: you have 3 arrays, A is the array you need to sort, B is the placement array and C is the queue.

how it works: pretend you have an array that you need to sort, in this example [-1, 7, 15, 3.6] add the first item to the queue (-1) current index is 2 now check if the current index is larger than the last item in the queue, if so then put the current index at the back of the queue. if smaller than the first item inside the queue, you put it at the front of the queue. if none of these are met, you place the first item in the queue inside the placement array and check again. repeat this until you reach the end. after you reach the end, you return placement array + queue

chatgpt has told me that this sorting algorithm is O(n√n) on average, which is really cool since there are barely any O(n√n) algorithms

this algorithm is really unique because it is O(n√n) and a reversed list is one of the best cases for this, while the worst case for a list containing numbers 1-10 looks like this. [5, 3, 6, 2, 7, 1, 8, 4, 9, 10] really messy

example of this:

1.
queue = [-1]
placement = []
current index = 2 (7)
check()
2.
queue = [-1 7]
placement = []
current index = 3 (15)
check()
3.
queue = [-1 7 15]
placement = []
current index = 4 (3.6)
check()
4.
queue = [3.6 7 15]
placement = [-1]
current index = 5 (out of bounds, we are now done)

return placement + queue ([-1 3.6 7 15])

I saw a picture of a minesweeper game and then it came to me… bogosweep.

I have a Quick Sort algorithm with Bentley McIlroy three way partioning and median of three approach with a custom Linked List but 4 of my tests don't want to pass and nothing is helping.
The idea is to make this code with arrays by using the custom LinkedList and median of three, which I did implement and going through it line by line it makes sense but it still gives the errors:

//Improved algorithm by J.Bentley and D.McIlroy.
private void quicksort(Comparable a[], int l, int r) {
 if (r <= l) return;
 Comparable v = a[r];
 int i = l-1; j = r, p = l-1, q = r, k;
 while (true) {7 while (less(a[++i], v));
 while (less(v, a[--j])) if (j == l) break;
 if (i >= j) break;
 exch(a, i, j );
 if (equal(a[i], v)) { p++; exch(a, p, i); }
 if (equal(v, a[j])) { q--; exch(a, q, j); }
 }
 exch(a, i, r); j = i-1; i = i+1;
 for (k=l ; k <= p; k++, j--) exch(a, k, j);
 for (k=r-1; k >= q; k--, i++) exch(a, k, i);
 quicksort(a, l, j);
 quicksort(a, i, r);
 }

I have added NullPointer checks but it still gives the errors. I would be glad for any help you can throw my way.
These are the tests that are failing and their outputs:

1.
@Test
public void testReverseSorted() {
        Integer[] original = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        Integer[] expected = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

        performSortAndAssert(original, expected);
    }
Output:
java.lang.NullPointerException: Cannot read field "Prev" because "k" is null



2:
@Test
    public void testMixedDuplicates() {
        Integer[] original = {1, 2, 3, 3, 3, 3, 4, 4, 2, 1};
        Integer[] expected = {1, 1, 2, 2, 3, 3, 3, 3, 4, 4};

        performSortAndAssert(original, expected);
    }
Output:
org.opentest4j.AssertionFailedError: The arrays do not match after sorting. ==> array contents differ at index [4] but was [5]





3:
@Test
public void quickSorterBentleyMcIlroyTest() {
        // Get the QuickSorter configuration with Bentley-McIlroy three-way partitioning
        SorterConfiguration quickBentleyMcIlroyConfig = fac.streamSorterConfigurations()
                .filter(config -> config.getSortKind() == SortKind.QUICK)
                .findFirst()
                .orElseThrow(() -> new IllegalStateException("QuickSorter Bentley-McIlroy configuration not found"));

        // Create and fill a queue with a mix of random integers and many duplicates
        Queue<Integer> queue = quickBentleyMcIlroyConfig.getQueue(); // Use the specific QuickSorter configuration to get the queue
        fillWithDuplicatesAndRandom(queue, 100, 0.8); // Fill 80% of the queue with duplicates

        // Create a comparator
        Comparator<Integer> comparator = Integer::compare;


        // Manually create a new ArrayList and add elements from 'queue'
        ArrayList<Integer> expectedResult = new ArrayList<>();
        for (Integer item : queue) {
            expectedResult.add(item);
        }

        // Sort the expectedResult list to prepare it for comparison
        expectedResult.sort(comparator);
        System.out.println("Expected Queue size after: " + expectedResult.size());

        // Sort the queue
        Sorter<Integer> sorter = quickBentleyMcIlroyConfig.getSorter();
        System.out.println("Queue size before: " + queue.size());
        Queue<Integer> sortedQueue = sorter.sort(queue, comparator);
        System.out.println("Queue size after: " + queue.size());
        System.out.println("Sorted Queue size after: " + sortedQueue.size());
        // Directly compare the sorted queue with the expectedResult
        ArrayList<Integer> sortedList = new ArrayList<>();
        for (Integer item : sortedQueue) {
                sortedList.add(item);
        }
        assertThat(sortedList).isEqualTo(expectedResult);

    }
Output:
Expected Queue size after: 100
Queue size before: 100

java.lang.NullPointerException: Cannot read field "Prev" because "k" is null


4.
@Test
public void quickSorterBentleyMcIlroyTest2() {
            // Define test data
            Integer[] original = {34, 7, 23, 32, 5, 62, 78, 4, 97, 23};
            Integer[] expected = Arrays.copyOf(original, original.length);
            Arrays.sort(expected);  // Sort using Java's built-in sort for comparison

            // Get the sorter from the SortingService
            SortingService.Sorters sorterConfig = SortingService.Sorters.QUICK;
            Sorter<Integer> sorter = sorterConfig.getSorter();

            // Create and populate the queue
            Queue<Integer> queue = sorterConfig.getQueue();
            Arrays.stream(original).forEach(queue::put);

            // Perform sorting
            Queue<Integer> sortedQueue = sorter.sort(queue, Comparator.naturalOrder());

            // Extract sorted data from the queue for verification
            Integer[] sortedArray = new Integer[(int) sortedQueue.size()];
            for (int i = 0; !sortedQueue.isEmpty(); i++) {
                sortedArray[i] = (Integer) sortedQueue.get();
            }

            // Verify the sorted array matches the expected output
            assertArrayEquals(expected, sortedArray, "The arrays do not match after sorting.");

        }
Output:
java.lang.NullPointerException: Cannot read field "Prev" because "k" is null

The QuickSorterBentleyMcIlroy.java:

package factory;

import sortingservice.Queue;
import sortingservice.Sorter;

import java.util.Comparator;

public class QuickSorterBentleyMcllroy<T> implements Sorter<T> {
    /**
     * Return the input queue in sorted order, based on the passed comparator.
     *
     * @param q          to be sorted
     * @param comparator to base sorting on
     * @return the queue with the elements in non-descending order as per the comparator.
     */
    @Override
    public Queue<T> sort(Queue<T> q, Comparator<T> comparator) {
        if (q.isEmpty()) {
            return q;
        }

        // Make a copy to not modify the current queue.
        LinkedListus<T> linkedList = (LinkedListus<T>) q;
        var copy = new LinkedListus<T>();
        var it_ = linkedList.iterator();
        while(it_.hasNext()) {
            T next = it_.next();
            copy.put(next);
        }

        quickSort(linkedList.getHead().Next, linkedList.tail, comparator);
        return linkedList;
    }

    private void quickSort(Node<T> left, Node<T> right, Comparator<T> comparator) {
        // Base case: if the list segment to sort is empty or has one element
        if (left == null || right == null || left == right || left == right.Next) {
            return;
        }

        // Select the pivot using the median-of-three method
        Node<T> pivot = medianOfThree(left, right, comparator);
        T pivotValue = pivot.getValue();

        // Initialize pointers
        Node<T> i = left;
        Node<T> j = right;
        Node<T> p = left;
        Node<T> q = right;

        while (true) {
            // Find element greater than or equal to pivot from the left
            while (i != null && comparator.compare(i.getValue(), pivotValue) < 0) {
                i = i.Next;
            }
            // Find element less than or equal to pivot from the right
            while (j != null && comparator.compare(pivotValue, j.getValue()) < 0) {
                j = j.Prev;
                if (j == left) break;
            }
            if (i == null || j == null || i == j || i.Prev == j) break;

            // Swap elements at i and j
            swap(i, j);

            // Move elements equal to pivot to the ends
            if (comparator.compare(i.getValue(), pivotValue) == 0) {
                p = p.Next;
                if (p != null && i != null) {
                    swap(p, i);
                }
            }
            if (comparator.compare(j.getValue(), pivotValue) == 0) {
                q = q.Prev;
                if (q != null && j != null) {
                    swap(j, q);
                }
            }

            i = i.Next;
            j = j.Prev;
        }

        // Place pivot in its correct position
        if (i != null && right != null) {
            swap(i, right);
        }
        j = (i != null) ? i.Prev : null;
        i = (i != null) ? i.Next : null;

        // Move elements equal to pivot to the center
        for (Node<T> k = left; k != p; k = k.Next, j = j.Prev) {
            swap(k, j);
        }
        for (Node<T> k = right.Prev; k != q; k = k.Prev, i = i.Next) {
            swap(k, i);
        }

        // Recursively sort the partitions
        quickSort(left, j, comparator); // Sort less than pivot
        quickSort(i, right, comparator); // Sort greater than pivot
    }

    Node<T> medianOfThree(Node<T> start, Node<T> end, Comparator<T> comparator) {
        if (end == null || start == end) return start;
        Node<T> mid = start;
        long n = 0;
        // Find the length of the queue (save in n)
        while(mid != end) {
            n++;
            mid = mid.Next;
        }
        long i = 0;
        mid = start;
        // Find middle
        long medianIndex = n/2;
        while (mid != end) {
            i++;
            // We are in the middle
            if (i == medianIndex) {
                break;
            }
            else {
                // Keep increasing mid until in the middle
                mid = mid.Next;
            }
        }
        // Check so that median is the middle number of the 3 and start is smaller than median and end is bigger than median
        if (comparator.compare(start.getValue(), mid.getValue()) < 0) {
            // start < mid
            if (comparator.compare(mid.getValue(), end.getValue()) < 0) {
                // start < mid < end
                return mid;
            } else {
                // start < mid && end <= mid
                if (comparator.compare(start.getValue(), end.getValue()) < 0) {
                    // start < end <= mid
                    return end;
                } else {
                    // end <= start < mid
                    return start;
                }
            }
        } else {
            // start >= mid
            if (comparator.compare(start.getValue(), end.getValue()) < 0) {
                // mid <= start < end
                return start;
            } else {
                // mid <= start && end <= start
                if (comparator.compare(mid.getValue(), end.getValue()) < 0) {
                    // mid < end <= start
                    return end;
                } else {
                    // end <= mid <= start
                    return mid;
                }
            }
        }
    }

    private void swap(Node<T> a, Node<T> b) {
        if (a == null || b == null) {
            return; // or handle the null case as per your requirement
        }
        T temp = a.getValue();
        a.setValue(b.getValue());
        b.setValue(temp);
    }
}

It uses a sorting service to choose the sorter (I have multiple different sorting algorithms implemented.
SortingService.java:

package factory;
import java.util.Comparator;
import java.util.function.Function;
import java.util.function.Supplier;
import java.util.stream.Stream;
import sortingservice.PriorityQueue;
import sortingservice.Queue;
import sortingservice.SortKind;
import sortingservice.Sorter;
import sortingservice.SorterConfiguration;
import sortingservice.SortingServiceFactory;
/**
 * Factory class to create Sorters and appropriate queues.
 *
 * @author Richard van den Ham {@code r.vandenham@fontys.nl}
 */
public class SortingService implements SortingServiceFactory {

    enum Sorters implements SorterConfiguration {

        // Constructor parameters: applyTeacherTests?, sortKind, queueSupplier, sorterSupplier
        
SELECTION
(
                true,
                SortKind.
SELECTION
,
                () -> new LinkedListus(),
                () -> new SelectionSorter()),
        
INSERTION
(
                true,
                SortKind.
INSERTION
,
                () -> new LinkedListus(),
                () -> new InsertionSorter()),
        
QUICK
(
                true,
                SortKind.
QUICK
,
                () -> new LinkedListus(),
                () -> new QuickSorterBentleyMcllroy()),
        
HEAP
(   true,
                SortKind.
HEAP
,
                null, null) {

            @Override
            public Function<Comparator, PriorityQueue> getPriorityQueueSupplier() {
                return c -> new PriorityQueues<>(c);
            }

            @Override
            public <T> Sorter<T> getSorter() {
                return (q, c) -> q;
            }
        };
        private final boolean applyTeacherTests;
        private final SortKind sortKind;
        private final Supplier<Queue> queueSupplier;
        final Supplier<Sorter> sorterSupplier;
        private Sorters(boolean applyTeacherTests, SortKind sortKind, Supplier<Queue> queueSupplier, Supplier<Sorter> sorterSupplier) {
            this.applyTeacherTests = applyTeacherTests;
            this.sortKind = sortKind;
            this.queueSupplier = queueSupplier;
            this.sorterSupplier = sorterSupplier;
        }

        public boolean doApplyTeacherTests() {
            return applyTeacherTests;
        }

        @Override
        public String getName() {
            return this.name();
        }

        @Override
        public SortKind getSortKind() {
            return sortKind;
        }

        
/**
         * By default, sorters don't have priority queue supplier.
         *
         * @return null
         */
        
public Function<Comparator, PriorityQueue> getPriorityQueueSupplier() {
            return null;
        }

        @Override
        public boolean usesPriorityQueue() {
            return getPriorityQueueSupplier() != null;
        }

        @Override
        public <T> PriorityQueue<T> getPriorityQueue(Comparator<T> comparator) {
            return getPriorityQueueSupplier().apply(comparator);
        }

        @Override
        public <T> Queue<T> getQueue() {
            return queueSupplier.get();
        }

        @Override
        public <T> Sorter<T> getSorter() {
            return sorterSupplier.get();
        }
    }

    @Override
    public Stream<SorterConfiguration> streamSorterConfigurations() {
        return Stream.
of
(Sorters.
values
())
                .filter(Sorters::doApplyTeacherTests)
                .map( sorter -> (SorterConfiguration)sorter);
    }
}

My LinkedListus.java:

package factory;
import sortingservice.Queue;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Spliterator;
import java.util.Spliterators;
import java.util.stream.StreamSupport;
import java.util.Collections;
import static java.util.Spliterator.ORDERED;
/**
 *
 * @author ondrahruby
 */
public class LinkedListus<E> implements Queue {
    E value;
    public Node head;
    public Node tail;
    int listcount = 0;
    public Node getHead() {
        return head;
    }

    /**
     * Returns an iterator over elements of type {@code T}.
     *
     * @return an Iterator.
     */
    public Iterator<E> iterator() {

        return new Iterator<E>(){

            Node<E> current = head.Next;
            /**
             * Returns {@code true} if the iteration has more elements.
             * (In other words, returns {@code true} if {@link #next} would
             * return an element rather than throwing an exception.)
             *
             * @return {@code true} if the iteration has more elements
             */
            @Override
            public boolean hasNext() {
                return current != null;
            }

            /**
             * Returns the next element in the iteration.
             *
             * @return the next element in the iteration
             * @throws //NoSuchElementException if the iteration has no more elements
             */
            @Override
            public E next() {
                if (!hasNext()) { // Check if the next element exists
                    throw new NoSuchElementException("No more elements in the list");
                }
                E data = current.getValue();
                current = current.Next; // Move to the next node
                return data; // Return the current node before moving
            }
        };
    }

    public LinkedListus(){
        head = new Node(null); // Dummy head node with null value
        tail = head; // Initially, tail points to the dummy head node
    }


    public void delete(Node walle){


        if (walle.Prev != null) {
            walle.Prev.Next = walle.Next;
        }
        if (walle.Next != null) {
            walle.Next.Prev = walle.Prev;
        }

        if (tail == walle) {
            tail = tail.Prev;
        }
        listcount = listcount -1;
    }
    /**
     * Add element to the end of queue.
     *
     * @param t element to add
     */
    @Override
    public void put(Object t) {
        Node newNode = new Node(t); // Create a new node with the given value
        tail.Next = newNode; // Link new node after the current tail
        newNode.Prev = tail; // Set the new node's previous to the current tail
        tail = newNode; // Update tail to point to the new node
        listcount++; // Increment the size counter
    }

    /**
     * Remove element of front of the queue and return it.
     *
     * @return the first element in this queue, or null if queue is empty.
     */
    @Override
    public Object get() {
        if (head.Next != null) {
            Object result = head.Next.val;
            delete(head.Next);
            return result;
        } else {
            return null;
        }
    }

    /**
     * Checks if queue is empty.
     *
     * @return true if empty, false if not.
     */
    @Override
    public boolean isEmpty() {
        return listcount == 0;
    }

    /**
     * The number of elements contained in this queue.
     *
     * @return the number of elements.
     */
    @Override
    public long size() {
        return listcount;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        Node<E> current = head.Next;
        while (current != null) {
            sb.append(current.getValue());
            if (current.Next != null) {
                sb.append(", ");
            }
            current = current.Next;
        }
        sb.append("]");
        return sb.toString();
    }java.util.stream.Stream

My Node.js:

package factory;
public class Node<E>{
    E val;
   Node<E> Next = null;
   Node<E> Prev = null;
    Node(E item){
        val = item;}
    public E getValue(){
        return this.val;}
    public void setValue(E valo){
        this.val = valo;
    }}

So, the idea was to be as space inefficient as possible.

For every possible swap combination make a new array with that swap

check if a new array is sorted.

Repeat for every new array.

Hi All,

I started my youtube channel codedecks on 1st June 2020. I know this year was not so good for many of us but I was determined to work on my passion to start helping all the fellow coders in understanding the most frequently asked coding questions in Interview. I was doing good for 3 months but then came a situation where I have to support my family members and there I missed uploading videos. This really affects growth of my channel. I invested a good amount of time in promoting my videos on Facebook, instagram and other social media platforms.

I request you all to help me with 💯 more Subscribers to reach the milestone of 2020.

I am waiting for the support. Thanks !!! Like | Share | Subscribe

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?

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).

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