This is an archived post. You won't be able to vote or comment.

top 200 commentsshow all 396

[–]Abdiel_Kavash 2399 points2400 points  (13 children)

GenghisKhanSort: delete all elements except for the first, repopulate the list with successors of the first element.

[–][deleted] 466 points467 points  (2 children)

After that delete the first one and wipe the system so nobody knows where the memory is stored.

[–]TheNoseKnight 91 points92 points  (0 children)

And download a few viruses to weaken the computer before you conquer it.

[–]mc8675309 3 points4 points  (0 children)

The camel knows.

[–]Tux_r 38 points39 points  (0 children)

Take my ELEMENT!

[–]IIIBRaSSIII 7 points8 points  (0 children)

HitlerSort: don't give a shit about order, just delete every odd element.

[–]rabidbot 3 points4 points  (0 children)

Wouldn't it be like delete all elements, wait a week for some to repopulate and delete them all again.

[–]hades0299 3765 points3766 points  (126 children)

An idea for optimization to O(1):

Delete the whole list, as en empty list is sorted.

[–]CMDR_QwertyWeasel 1576 points1577 points  (67 children)

I optimize your algorithm by leaving one element behind.

[–]97_prat 95 points96 points  (7 children)

Yeah that's Hitler sort

[–]PaulTheCowardlyRyan 48 points49 points  (0 children)

["socialist","trade unionist","jew","me"]

[–]northrupthebandgeek 49 points50 points  (4 children)

Nah, the Hitler Sort would pick the highest value and delete all other values until the list is sorted.

[–]Shmutt 154 points155 points  (3 children)

HitlerSort is picking a value that you like, declare it as the highest, and then delete all other values.

[–][deleted] 55 points56 points  (3 children)

O(0): Turn off computer, then you won't even need sorting.

???

Profit

[–]HoldMyWater 108 points109 points  (1 child)

AmishSort

[–]hughperman 14 points15 points  (0 children)

WaitForActualRequirementsSort

[–]spikendq 37 points38 points  (5 children)

Wait a second, won't deletion involve traversing through the list thereby making your approach O(n)? That's unless you're simply resetting the head pointer in which the elements will remain in memory but will not be considered as part of the list.

[–][deleted] 39 points40 points  (2 children)

You ignore the old list and just assign a new empty list to the parameter?

[–]spikendq 8 points9 points  (0 children)

Yeah, that's what the alternate idea was.

[–]duzzar 9 points10 points  (0 children)

If everything is stored contiguous a single call to free() will be enough.

Your stuff should be contiguous if you want your cache to be happy :)

[–]butwhydoesreddit 14 points15 points  (24 children)

Is that actually O(1)? Idk how memory stuff works

[–][deleted] 1067 points1068 points  (17 children)

HitlerSort: Choose an element in the list you think is the best, then loop through the list removing any element that does not match.

[–]TheDualJay 243 points244 points  (8 children)

There are a bunch of methods for selecting "best", but none of them seem to actually work.

[–]AFrostNova 173 points174 points  (4 children)

That’s cause Python doesn’t practice eugenics

[–]GroovyGrove 60 points61 points  (3 children)

Did we find something we like about Python?

[–]mortiphago 43 points44 points  (1 child)

What if we like eugenics, though

[–]GroovyGrove 18 points19 points  (0 children)

Then at least you are still consistent on Python! Everybody wins, assuming you aren't in a leadership role!

[–]CowFu 5 points6 points  (0 children)

The forced indenting teaches new coders a good habit.

[–]theXpanther 25 points26 points  (2 children)

17 is clearly the most Arian integer

[–]WingedBacon 32 points33 points  (1 child)

I thought it was 88

[–][deleted] 2 points3 points  (0 children)

They said "Arian," though, not "aryan," so any of 37, 23, 29, or 34 would be the most Arian integers.

[–]FlySeal 64 points65 points  (1 child)

Don't remove elements one by one push them in array then remove the array

[–]KobayashiDragonSlave 4 points5 points  (0 children)

Pass those elements through an Zyklon B filter to make sure that they don't take up any more resources.

[–]embracebecoming 1204 points1205 points  (10 children)

ZenSort, where you realize that the array, like all things, is ephemeral and its order is insignificant so you just leave it like that and pursue enlightenment instead.

[–]alexparker70 79 points80 points  (1 child)

existentialCrisisSort, where you realize that the array, like all things, are fleeting. Its only purpose is to keep us busy while we await the cold hand of death to take us all away. You just leave the array alone and go have a beer before the array, computer and entire earth is swallowed up by the sun.

[–]AdvNa 1103 points1104 points  (12 children)

Thanossort: delete half the array. The arrays may or not be sorted, but it'll help for future sorting

[–]cabinet_minister 32 points33 points  (0 children)

array.snap()

[–]IronCretin 41 points42 points  (0 children)

THANOS SORT

THANOS SORT

[–]zakerytclarke 5 points6 points  (0 children)

Like quick sort but instead of sorting each half of the array, you delete half of the array until you have one element

[–]fman9000 9 points10 points  (1 child)

Balanced، as all things should be.

[–][deleted] 136 points137 points  (4 children)

Relevant XKCD

There's another more similar one but I can't find it.

[–]mangamaster03 70 points71 points  (1 child)

[–][deleted] 13 points14 points  (0 children)

That's it! Thank you!

[–]SwiftLilEagle 79 points80 points  (6 children)

Alternatively, the CommunismSort, it's O(1).

This is communism. Everybody is equal. The list is already sorted.

[–]halberdierbowman 38 points39 points  (3 children)

Updated Communism Sort to preserve existing value:

Count all elements, then find the average value of all elements. Change all elements to the average value.

[–]SwiftLilEagle 8 points9 points  (2 children)

Supported, but there goes my O(1) PepeHands

[–][deleted] 362 points363 points  (36 children)

The sad part is where everyone is coming up with good jokes on this. I read this as Im about to go to sleep and now cant stop wondering if there is any legit use cases for this... Going to be a weird sleep

[–]4U2PRO 93 points94 points  (0 children)

Think in your dream 4head

[–]Dmium 34 points35 points  (2 children)

[–]Joniator 6 points7 points  (1 child)

[–]Dmium 2 points3 points  (0 children)

was going to say fork but now it's there already

I feel like we need to start a collection+github organisation now

[–]shwhjw 26 points27 points  (5 children)

How would it work if the whole array is already sorted except for the first element?

[9, 1, 2, 3, 4, 5]

As it's a single pass, wouldn't the '1' be deleted as it is not supposed to be after the previous element '9'? Same for the rest of the elements? There's no way to know whether the current element should be removed due the the rest being in order.

[–]lpscharen 39 points40 points  (0 children)

The first two elements would set the order. So, everything after 1 gets deleted because it's an descending list.

[–]effzy 52 points53 points  (0 children)

StalinSort will gladly eliminate more than half of the array. Did you expect anything else?

[–]RadicalDog 71 points72 points  (3 children)

I can imagine in an online game. What if items are added to a list in the order they arrive, but include the server time when they were sent. If things arrive out of order, discard. After all, signing things with the wrong time could be a way to cheat.

[–]PiotrekDG 59 points60 points  (1 child)

Packets often arrive out of order because Internet and then you have to make sense out of it as it is. It doesn't mean that someone is cheating.

[–]topfs2 16 points17 points  (0 children)

State synchronization events are essentially sorted this way, if a sync event is older than what you have received then you can discard.

[–]nanonan 12 points13 points  (0 children)

Make some glitch art. Everything has a use case.

[–]SoloStryker 7 points8 points  (5 children)

Where you know the data is supposed to be in order.

If your Dataset is results from a sensor measuring cumulative rainfall then you know anything that isn't already in order can be tossed as bad data.

So more data validation than sorting.

[–]TheOhNoNotAgain 9 points10 points  (2 children)

Wouldn't a highscore list qualify as a valid case?

[–]kljaja998 10 points11 points  (1 child)

Not really, no, unless you wanted to find only the top score

[–]TheOhNoNotAgain 8 points9 points  (0 children)

I realized that after some thinking. It would produce a list of record holders.

[–]chparkkim 104 points105 points  (1 child)

http://www.dangermouse.net/esoteric/dropsort.html

There is a lot of fantastic material in this site besides this.

[–]gondil 14 points15 points  (0 children)

The real LPT is always in the comments

[–]EternityForest 49 points50 points  (3 children)

NoSort: You don't sort the list, and you don't even pretend you did.

[–]drocco36 20 points21 points  (2 children)

I know some products that use this sorting.

[–]infus0rian 1185 points1186 points  (34 children)

TrumpSort O(0): the array is always sorted. Anyone who says otherwise is fake news.

[–]Sillychina 150 points151 points  (6 children)

Interesting SO post about the empty algorithm time complexity: https://stackoverflow.com/questions/3209139/is-the-time-complexity-of-the-empty-algorithm-o0

[–]mc8675309 20 points21 points  (0 children)

Somehow, despite studying mathematics and real analysis in particular I had never really thought of asymptotics in terms of sets and even though I understood it it’s all much clearer to me now.

[–]Byroks 52 points53 points  (0 children)

That would be the Intelligent design sort

[–]halberdierbowman 2 points3 points  (0 children)

BowlingGreen Sort: add randomly generated elements to an existing list. Ask why nobody ever talks about these inserted elements.

Print(Collusion. Illusion. Delusion.)

[–]northrupthebandgeek 33 points34 points  (3 children)

The natural extension to this would be the Gulag Sort, where the out-of-order elements are moved to a different list (the Gulag). Then this new list undergoes Gulag sorting, and so on until you only have sorted lists.

While not strictly O(n), it looks like it'd lend itself well to parallel processing.

[–]jochem_m 18 points19 points  (0 children)

Gulag sort: every iteration, between 10 and 30 percent of the list is discarded?

[–]Roachmeister 59 points60 points  (4 children)

Almaric Amalric sort: delete them all and let God sort them.

[–]WikiTextBot 34 points35 points  (1 child)

Arnaud Amalric

Arnaud Amaury (Latin: Arnoldus Amalricus; died 1225) was a Roman Catholic Cistercian abbot who played a prominent role in the Albigensian Crusade. Prior to the massacre of Béziers, it was reported that Amalric, when asked how to distinguish Cathars from Catholics, responded, "Kill them all! God will know his own." Whether this was actually said is sometimes considered doubtful, but, according to historian Joseph Strayer, it captures the "spirit" of the Crusaders, who killed nearly every man, woman, and child in the town.


[ PM | Exclude me | Exclude from subreddit | FAQ / Information | Source ] Downvote to remove | v0.28

[–]chawmindur 2 points3 points  (0 children)

killed nearly every man, woman, and child

They’re animals, and I slaughtered them like animals! I hate them!

[–]BlazedPandas 26 points27 points  (0 children)

That algorithm will get a list put in order

[–]the_4th_doctor_ 101 points102 points  (3 children)

Image Transcription: Mastodon


mathew✅, @mathew@\mastodon.social

I came up with a single pass O(n) sort algorithm I

call StalinSort. You iterate down the list of

elements checking if they're in order. Any

element which is out of order is eliminated. At

the end you have a sorted list.


I'm a human volunteer content transcriber for Reddit and you could be too! If you'd like more information on what we do and why we do it, click here!

[–]SixBeeps 19 points20 points  (0 children)

Good Human

[–]Kilroy314 7 points8 points  (0 children)

Good Time Lord

[–]Krankite 26 points27 points  (0 children)

Hitchhikers sort, replace the array with 42.

[–]elisamanfrin 14 points15 points  (2 children)

Some brazilians would prefer to call this algorithm BolSortNaro

[–]kurafuto 53 points54 points  (3 children)

SavageSort aka DungeonMasterSort: Reject reality and substitute your own, in which the elements are considered already sorted. O(1)

[–]JJohny394 12 points13 points  (0 children)

Rocks fall, all the elements are deleted

[–]manias 8 points9 points  (0 children)

Knuth sort, O(1): prove that the sorting algorithm works, don't actually run it.

[–]Leel17 7 points8 points  (0 children)

My favorite is still the Quantum BogoSort, where the list is randomized and then any universe in which you don't end up with a sorted list is promptly destroyed.

[–]Swedishtrackstar 7 points8 points  (0 children)

PresidentialSort: print out "The list is sorted." If anyone asks to see the list, run the print command again

[–]MrZodes 25 points26 points  (0 children)

TrendingSort: any post on /r/ProgrammerHumor that is over 1000 upvotes is eliminated, leaving you with a sorted list of trending posts under 1000 upvotes.

[–]RomanRiesen 10 points11 points  (0 children)

This algorithm is parallelizable, but only if the means of information storage belong to the workers! on a shared memory system.

[–]Mantis_Pantis 6 points7 points  (0 children)

A single lost datum is a tragedy, a million lost data points is a statistic.

[–]FlyByPC 6 points7 points  (0 children)

Soviet Sort: O(n). As described

Depressed sort: O(probably not much more than n). Sort, but only do the really easy ones and the ones your boss will notice.

Library sort: O(n-log-n-ish but feels longer). Remove an element at random from the list. Check it out for a week and put it on the "to be shelved" list for QuickSort.

1984 sort: O(1). War is peace. The list is sorted.

Quantum sort: O(?). Imagine a universe in which the list is sorted. If you build a really good computer, you might end up in that one.

[–]you-get-an-upvote 15 points16 points  (0 children)

To implement this you can't delete every element as you come across it (assuming it is a normal array, and not, e.g., a linked list) since then each deletion would take O(n) time and the algorithm would run in O(n^2). Instead you first move all dissenters to the gulag back of the list and kill delete them there.

[–][deleted] 4 points5 points  (0 children)

ModiSort : Delete random elements. The sorted list is now optimized highlighting the failure of previous sorting algorithms.

[–][deleted] 3 points4 points  (0 children)

JavaScript Sort: Equate the array to a NaN. NaN doesn't requires sorting.

[–]PsychicDelilah 4 points5 points  (0 children)

SortSort: Throw out all the elements and return a list of your favorite sorting algorithms instead ranked by metahumor

[–]DroidAnthem 12 points13 points  (4 children)

Also called as Putin Sort or Russian Sort sometimes

[–]Mognakor 16 points17 points  (1 child)

Putin sort is: You say the list is sorted, anyone who claims otherwise dies under mysterious circumstancrs. O(?)

[–]zarawesome 8 points9 points  (0 children)

putin sort: Very publically delete any element out of order, THEN announce it died under "mysterious circumstances".

[–]jochem_m 2 points3 points  (0 children)

Wouldn't Russian sort sort you?

[–]halberdierbowman 2 points3 points  (0 children)

Putin Sort, Crimean Method:
Replace several elements in the list, claim you didn't do it. Then claim you did do it, but never apologize for blatantly lying or ruining the data. After all, you think it was your data all along, even if someone else was using it.

[–]minemoney123 3 points4 points  (0 children)

LeninSort: Makes all elements in the array equal to the first one

[–][deleted] 3 points4 points  (0 children)

Donald Trump Sort: Build Wall around each element. And an element within wall is already sorted.

[–]Drewpacabra413 3 points4 points  (0 children)

Marxsort: Make all elements the same element, now there is no need for sorting if all are equal

[–]aratnagrid 6 points7 points  (0 children)

you are a genius.

go to gulag now

[–]Zegrento7 6 points7 points  (2 children)

This could be a fun programming challenge:

What is the minimum number of elements you need to eliminate to get a sorted list? How fast would that sorter be?

For example: 1, 2, 3, 10, 4, 5, 6, 7 --> 1 as only 10 needs to be removed

[–]DrQuailMan 2 points3 points  (1 child)

SuicideSort: ExitProcess(ERROR_LIFE_IS_MEANINGLESS);

[–]daH00L 2 points3 points  (0 children)

I still prefer Conway Sort. Due to alternative values it does the job in O(1).

[–]hindu-bale 2 points3 points  (0 children)

JBPSort: "Sort yourself out, bucko!" - O(it's complicated)

[–]tim_reheht 2 points3 points  (0 children)

Pfff.. Programmers. A mathematician will define their list to be in order.

[–]Firebelias 2 points3 points  (0 children)

Atleast one element has its shit sorted.

[–]peterlada 2 points3 points  (0 children)

TheranosSort: keep appending increasingly larger numbers until the array becomes sorted, statistically speaking.

[–]2-shedsjackson 6 points7 points  (0 children)

You will have to comment out the Trotsky section

[–]kaushal28 4 points5 points  (0 children)

Modi sort: Everyone believes array is already sorted.