Shell sort vs Insertion sort

Introduction of Shell sort, and a match with Insertion Sort.

For an introduction of Insertion sort, see:

Choosing the sequence 9-6-1:
For a list of size 10, the gaps can be any number 1,2,....,9, and the sequence must end with 1.
So each of the gaps 2,3,...,9 can be included in the sequence, or not included. So there's a total of 2^8=256 possible gap sequences. For each we checked the average number of comparisons for all possible 10! permutations.
Here are the 3 best sequences:
9-6-1: 25.512 comparisons
4-1: 25.516 comparisons
6-1: 25.539 comparisons

We could have also checked which has the highest probability of performing less comparisons than insertion sort. Here are the top 3 in this respect:
4-1: prob=0.72
9-4-1: prob=0.704
6-1: prob=0.701

Analyzing Shell sort variants more generally: See it explained in my home page:

Why did Shell sort lag behind in the second match in comparisons per second? You are welcome to post answers. Or read answer here:

[warpzone]

I like how the robots having to move the full distance between balls approximates the idea of data locality

[zorm_]

I love that 13 years after the first video you guys are still doing 3d animations with the exact same robot model

[SuperfieldCrUn]

While this may seem like it's a marginal improvement over insertion sort if you manage to crack the gap code, remember that we are only working with very small lists of 10 items at a time. Once you scale up the list to hundreds or thousands, it becomes a completely different ball game and things like shell sort kick insertion sort to the curb.

[offchan]

It's been over a decade since his first sorting video yet he is still interested in making sorting videos. Guys, dedicate to your friends and family like this guy dedicate to sorting algorithms.

[weecl]

for the question at 6:16, I think it's due to shell sort spending more time moving different elements from one place to another on the rack, whereas insertion sort was almost always holding one element and comparing others to it.

[zlodevil]

Shell sort is one of the most interesting sorting algorithms, im glad you’re making videos about it

[Polygonetwo]

Having watched a decade of sorting videos as if they were released as a series over the course of a week, the robots getting jet engines is hilarious and a wild plot twist.

Also the whole series is just well made and really shows off the differences in the algorithms.

[professorbrainstorminmemef]

The fact that this channel is still making these late 1990s-esque animations in the 21st century really keeps me going. Love these robots!

[TheAgentAPM]

I really like this lines display. Surely on Quick sort it would show at a glance how the first iteration partitions the set into two non-overlapping subsets.

[will]

I like these animations. They make the video easy and intuitive to understand.

[AustinSmith]

Thanks to these videos, I now understand the "sounds of sorting" videos YouTube keeps recommending me.

[flyingbicycles]

Upside: gets into O(nlogn) territory with the right gap sequence
Downside: you need to calculate that gap sequence ahead of time

[viperbeatz]

Finally, a new udiprod video! I've been waiting for so long lol

Good that the sorts are back

[icecreamsamwich]

The fact that you've used this same visualization for 10+ years with few changes is delightful to me

[heck_fy]

Wow, the coolest explanation and visualization of Shell sort I've seen! Thank you so much. So simple, short and clear explanation

[ruix]

Almost 10 years and still making these animations. Kings

[medexamtoolscom]

Insertion is best with actual physical objects, when making room to insert an object in is as simple as shoving everything to the right of it further to the right, rather than with computer memory, moving it over to the next memory address for each and every individual item in memory. With my DVD collection, inserting a movie between positions 23 and 24 out of 50 means shoving all DVD cases 24 through 50 together to the right by .5 inch all at once which can be done in one swift motion of a hand. While in a computer, that means moving the item in slot 50 to slot 51... then moving the item in slot 49 into slot 50, and then moving the item in slot 48 to slot 49... all the way down to then moving the item in slot 24 to slot 25, and then and only then having the space to put the new item into slot 24.

[KnownRed]

Babe wake up, new udiprod video just dropped

[NateTheOhioan]

I have a feeling that this is about to be recommended to everyone

[Um_Kaye]

I need more of this. I love coming back here from time to time to watch these guys sort!