data structures using shell sort shell sortinvented by donald shell in is sorting algorithm that is generalization of insertion sort while discussing insertion sortwe have observed two thingsfirstinsertion sort works well when the input data is 'almost sortedsecondinsertion sort is quite inefficient to use as it moves the values just one position at time shell sort is considered an improvement over insertion sort as it compares elements separated by gap of several positions this enables the element to take bigger steps towards its expected position in shell sortelements are sorted in multiple passes and in each passdata are taken with smaller and smaller gap sizes howeverthe last step of shell sort is plain insertion sort but by the time we reach the last stepthe elements are already 'almost sorted'and hence it provides good performance if we take scenario in which the smallest element is stored in the other end of the arraythen sorting such an array with either bubble sort or insertion sort will execute in ( time and take roughly comparisons and exchanges to move this value all the way to its correct position on the other handshell sort first moves small values using giant step sizesso small value will move long way towards its final positionwith just few comparisons and exchanges technique to visualize the way in which shell sort worksperform the following stepsstep arrange the elements of the array in the form of table and sort the columns (using insertion sortstep repeat step each time with smaller number of longer columns in such way that at the endthere is only one column of data to be sorted note that we are only visualizing the elements being arranged in tablethe algorithm does its sorting in-place example sort the elements given below using shell sort solution arrange the elements of the array in the form of table and sort the columns result the elements of the array can be given as repeat step with smaller number of long columns result the elements of the array can be given as repeat step with smaller number of long columns