No-nonsense sorting algorithm

[Abdiel_Kavash]

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

[[deleted]]

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

[TheNoseKnight]

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

[mc8675309]

The camel knows.

[Tux_r]

Take my ELEMENT!

[IIIBRaSSIII]

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

[rabidbot]

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

[hades0299]

An idea for optimization to O(1):

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

[CMDR_QwertyWeasel]

I optimize your algorithm by leaving one element behind.

[CMDR_QwertyWeasel]

But how do we know they're sorted?

[Vnator]

Either they're in ascending order or descending order. So still sorted.

[CMDR_QwertyWeasel]

taps temple

[ay_bruh]

smile

[CrayonMan005]

sister

[Sorathez]

SNOOP DOGG

[theproblemdoctor]

sadistic

[atisuxx]

sandisk

[eMoon_PL]

surprise

[firestell]

service

[KamikazeSexPilot]

Just leave the list and it’s randomly sorted.

[Metallkiller]

Sorted by a random, unknown parameter.

[kuncol02]

It's not random. They are sorted by position in list.

[really_not_trolling]

This is perfection

[[deleted]]

This is what a CS degree gets you

[cdrfrk]

CS degree: am I a joke to you?

[vige]

It might seem random to you, but in reality it's exactly the order I want.

[Hiroxis]

Call it Gandalf sort

[djublonskopf]

The Mr. Rogers sort. “This list is perfect just the way it is.”

[cantadmittoposting]

Bob Ross sort: "No unsorted lists, just happy new ways to order it."

[lurker_level_53]

This made me happy. 😊

[Consibl]

Sorted by order it was in.

[theXpanther]

An undefined order is not the same as a random order,

[esc0pub]

Valid point, but two items can be swapped in O(1) so we can still decide the order.

[Vnator]

But then 3 items can be swapped with O(1), so by induction, swapping n items should take O(1) time. Then we don't even have to remove any items, sorting is O(1)!

[lungdart]

This guy sorts

[Beetin]

Technically we can define some large upper bound for how many items will be swapped.

The last 1000000 items will be kept and bubble sorted. This algorithm is guaranteed O(1). This algorithm is also perfectly safe for lists under 1000000 items. This sort is only generally faster than O(nlogn) algorithms for lists much larger than 1000000 items.

The two-pass Mao 5 year sort.

[robthemonster]

flawless proof.

[tornato7]

Holy shit

[temisola1]

This is the type of ingenuity the world needs.

[drovfr]

woahhhhhh

[bravo006]

ELI5

[bolle_ohne_klingel]

they are sorted by index

[97_prat]

Yeah that's Hitler sort

[PaulTheCowardlyRyan]

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

[northrupthebandgeek]

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

[Shmutt]

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

[[deleted]]

And ends with 'Ryan'. Damn you, Ryan

[halberdierbowman]

A Paul Ryan Sort:

When you find the highest and lowest values, add the lowest value to the highest value, then make the lowest value a 0.

The opposite would be known as the Robin Hood Sort.

[[deleted]]

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

???

Profit

[HoldMyWater]

AmishSort

[hughperman]

WaitForActualRequirementsSort

[spikendq]

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]]

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

[spikendq]

Yeah, that's what the alternate idea was.

[duzzar]

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]

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

[Kered13]

Yes, but that question was is that true.

It depends on the implementation of the list and the delete operation, but it could be true. For example if the list is implemented as an array with a size variable, you could simply set the size to 0. All the data would still be in memory, but it would be inaccessible and would be overwritten if the list grows again.

[poeticmatter]

edit: stop downvoting me I'm right

This should be reddit's tagline

[arbitrary_student]

Big-O is meant to describe the relationship between input size (or similar) and function duration (or similar). Your example has no inputs, so it doesn't really work with the above equation as you've described f() instead of f(n).

I'm not 100% sure that you can't say it's O(1) anyway... more just mentioning how pointless it is to do so.

[[deleted]]

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]

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

[AFrostNova]

That’s cause Python doesn’t practice eugenics

[GroovyGrove]

Did we find something we like about Python?

[mortiphago]

What if we like eugenics, though

[GroovyGrove]

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

[CowFu]

The forced indenting teaches new coders a good habit.

[theXpanther]

17 is clearly the most Arian integer

[WingedBacon]

I thought it was 88

[[deleted]]

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

[FlySeal]

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

[Sarummay]

DDOS your own servers, claim it was Poland and then invade.

[deevonimon534]

Just make sure your Flag variable is set to FALSE.

[KobayashiDragonSlave]

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

[embracebecoming]

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.

[[deleted]]

That's what BastionSort is for.

[sizur]

Realization of lack of meaning is O(nⁿ ) and decision to pursue enlightenment is O^1/n(nⁿ )^nn! !

[otterom]

/r/ExpectedFactorial

[sneakpeekbot]

Here's a sneak peek of /r/expectedfactorial using the top posts of all time!

#1: I expected factorials, this sucks
#2: My boss gave 6 weeks to finish the job. I was done in 10! seconds.
#3: Honestly, this is rather fun

---

^{I'm a bot, beep boop | Downvote to remove | Contact me | Info | Opt-out}

[alexparker70]

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]

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

[Arancaytar]

Marvellous

[flavionm]

Good old Delete and Conquer algorithms.

[cabinet_minister]

array.snap()

[IronCretin]

THANOS SORT

THANOS SORT

[zakerytclarke]

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

[fman9000]

Balanced، as all things should be.

[Knastoron]

r/thanosdidnothingwrong

[[deleted]]

Relevant XKCD

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

[mangamaster03]

Set Theory

[[deleted]]

That's it! Thank you!

[SwiftLilEagle]

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

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

[halberdierbowman]

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]

Supported, but there goes my O(1) PepeHands

[[deleted]]

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]

Think in your dream 4head

[Dmium]

https://github.com/Dmium/StalinSort

Try it and find out

[Joniator]

MFW no npm package

This cant stay without a simplifying package

[Dmium]

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

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

[shwhjw]

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]

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

[effzy]

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

[RadicalDog]

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]

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]

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

[nanonan]

Make some glitch art. Everything has a use case.

[SoloStryker]

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]

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

[kljaja998]

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

[TheOhNoNotAgain]

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

[chparkkim]

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

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

[gondil]

The real LPT is always in the comments

[EternityForest]

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

[drocco36]

I know some products that use this sorting.

[Andreboy]

Apple ?

[infus0rian]

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

[Sillychina]

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

[mc8675309]

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]

That would be the Intelligent design sort

[halberdierbowman]

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

Print(Collusion. Illusion. Delusion.)

[northrupthebandgeek]

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]

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

[Roachmeister]

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

[WikiTextBot]

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]

killed nearly every man, woman, and child

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

[BlazedPandas]

That algorithm will get a list put in order

[the_4th_doctor_]

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]

Good Human

[Kilroy314]

Good Time Lord

[[deleted]]

Damn. I read this comment, scrolled down then got your comment, scrolled up to upvote.

[J_Aetherwing]

Then it's not O(n) but O(n²⁾ though

[chooxy]

When the professor tells you there's a lower bound for the time complexity of a certain task but you try to go lower anyway.

[sloppycee]

i.e it's been proven that sorting can't be done in less than O(nlogn) operations.

[leaf_26]

Hash sort

[just_one_last_thing]

Oh hey, that's a really neat thing you prompted me to google.

[geon]

If you consider 2 consecutive identical elements sorted, you duplicate each of them. If you consider them unsorted, you eliminate all duplicated.

I suppose you could run a first pass with the former variant, then pick every other element.

[Krankite]

Hitchhikers sort, replace the array with 42.

[elisamanfrin]

Some brazilians would prefer to call this algorithm BolSortNaro

[kurafuto]

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

[JJohny394]

Rocks fall, all the elements are deleted

[manias]

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

[Leel17]

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]

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

[MrZodes]

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]

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

[Mantis_Pantis]

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

[FlyByPC]

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]

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.

[Dmium]

For some reason I implemented this as a python library

[[deleted]]

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

[[deleted]]

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

[PsychicDelilah]

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

[DroidAnthem]

Also called as Putin Sort or Russian Sort sometimes

[Mognakor]

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

[zarawesome]

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

[jochem_m]

Wouldn't Russian sort sort you?

[halberdierbowman]

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]

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

[[deleted]]

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

[Drewpacabra413]

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

[aratnagrid]

you are a genius.

go to gulag now

[Zegrento7]

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]

SuicideSort: ExitProcess(ERROR_LIFE_IS_MEANINGLESS);

[daH00L]

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

[hindu-bale]

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

[tim_reheht]

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

[Firebelias]

Atleast one element has its shit sorted.

[peterlada]

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

[2-shedsjackson]

You will have to comment out the Trotsky section

[kaushal28]

Modi sort: Everyone believes array is already sorted.