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