Shell sort

Bubble sort always compares an element to the neighboring element, but is this important? Many would say that it depends on the pre-existing order of the unsorted collection: are these future neighbors far apart or close together?

Donald Shell, the inventor of shell sort, must have had a similar idea and used a "gap" between elements to make further jumps with the swapping approach adopted by bubble sort. By utilizing a specified strategy to choose those gaps, the runtime can change dramatically. Shell's original strategy is to start with half the collection's length and, by halving the gap size until zero, a runtime of O(n²) is achieved. Other strategies include choosing numbers based on some form of calculation of the current ...

Get The Complete Rust Programming Reference Guide now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.