Shell Sort

The bubble sort algorithm compares immediate neighbors and exchanges them if they are out of order. If we have a partially sorted list, bubble sort should give reasonable performance as it will exit as soon as no more swapping of elements occurs in a loop.  

But for a totally unsorted list, sized N, you can argue that bubble sort will have to fully iterate through N-1 passes in order to get it fully sorted.

Donald Shell proposed Shell sort (named after him), which questions the importance of selecting immediate neighbors for comparison and swapping.

Now, let's understand this concept.

In pass one, instead of selecting immediate neighbors, we use elements that are at a fixed gap, eventually sorting a sublist consisting of a pair of data points. This is shown in the following diagram. In pass two, it sorts sublists containing four data points (see the following diagram). In subsequent passes, the number of data points per sublist keeps on increasing and the number of sublists keeps on decreasing until we reach a situation where there is just one sublist that consists of all the data points. At this point, we can assume that the list is sorted:

In Python, the code for implementing the Shell sort algorithm is as follows:

def ShellSort(list):     
    distance = len(list) // 2     
    while distance > 0:         
        for i in range(distance, len(list)):             
            temp = input_list[i]             
            j = i 
# Sort the sub list for this distance 
           while j >= distance and list[j - distance] > temp: 
              list[j] = list[j - distance] 
              j = j-distance            
          list[j] = temp 
# Reduce the distance for the next element         
        distance = distance//2
    return list

The preceding code can be used to sort the list, as follows:

Note that calling the ShellSort function has resulted in sorting the input array.