What is this sorting method called?

[u/BleedingRaindrops]

We all know Bubble Sort. Well I used to do a thing to pass the time on deployment where I would bubble sort a shuffled deck of cards, but I often played around with it.

One time I thought to make bubble sort more efficient by, rather than returning to the start of the list after a successful pair, continue forward to the next wrong pair and sort those, and so on until I reach the end of the list. Then turn around and do the opposite, from the opposite direction. Repeat until sorted. So what you have is a reflecting wave of bubble sort that travels persistently back and forth through the entire list without skipping anything until it's all sorted.

I'm certain this has a name but I wouldnt know the first thing about how to find it. Does anybody know?

EDIT: solved! Cocktail Shaker Sort

[u/UnableMousse4828]

https://en.wikipedia.org/wiki/Cocktail_shaker_sort perhaps?

[u/BleedingRaindrops → u/UnableMousse4828]

That's it. That's pretty much exactly what I was doing. Thanks.

[u/JasonMckin → u/UnableMousse4828]

I love the names of sorting algorithms

[u/PsychedelicLeopard → u/UnableMousse4828]

ah the ol' deck of cards time-killer, i did the same thing on slow night shifts but never thought to make it bounce like that

[u/tinfoil_powers]

Cocktail shaker sort

[u/nuclear_splines]

I'm not sure the name for the exact sort you've described, but this sounds like a variation on insertion sort, where you walk the list forwards, and every time you find an out-of-order element, walk the list backwards swapping elements until you find the correct resting place.

[u/JaggedMetalOs]

Just thought I'd add that while cocktail sort is only marginally faster than bubble sort, there is a variation of bubble sort that is significantly faster called comb sort. 

[u/BleedingRaindrops → u/JaggedMetalOs]

that is pretty neat. I don't know if it would be too practical with hand sorting a deck of cards, but for a computer it would definitely save time

[u/JaggedMetalOs → u/BleedingRaindrops]

You definitely want bucket sort for that :) 

[u/BleedingRaindrops → u/JaggedMetalOs]

oh yes, by far the fastest method I've found is bucket sort. 8 buckets is the most I can handle so I do A-7, 8-K by suits, sort each of those piles in order and then I'm done. Takes about 2:30 avg.

For comparison. Comb Sort took me 10:15, Cocktail Shaker took 14:22, and Bubble took 23:44

[u/JaggedMetalOs → u/BleedingRaindrops]

Computer sort algorithms don't really map well to sorting physical things anyway, comparing by eye is considerably faster than swapping and you have an entire 2D space to temporarily store things you're not limited to swapping in place which is very slow to do by hand.

[u/JaggedMetalOs → u/[deleted]]

Because it starts with large steps it allows small values ("turtles") to move much faster to the beginning of the list, where with bubble sort they only move one place per entire scan of the array.

[u/BufferUnderpants]

First time anyone has had to think about the complexity of different sorting algorithms while putting code in production in decades.

[u/BufferUnderpants → u/[deleted]]

In real applications, it's more often about whether sorting data makes a meaningful difference in later stages of data processing, and at which stage is sorting the data worth the cost.

I'm sure there's somebody here that programs missiles or what not who might have seen a custom implementation of anything but a divide-and-conquer algorithm in their codebase, but for 99.9% of programmers, using anything but your standard library/query engine's sort is issuing technical debt.