second_list [ ] [ ] [ ] [ [ third_list [ ] [ ] [ ] [ [ forth_list [ ] [ ] [ ] [ [ fifth_list [ ] [ ] [ ] [ [ notes so the sub list will contain every kth element of the original list starting from index - th according to the algorithm mentioned abovefor each iterationthe list is divided and then sorted if we use the same value of kwe will get the same sub lists and every time we will sort the same sub listswhich will not result in the ordered final list note that sorting the five sub lists independently do not ensure that the full list is sortedso we need to change the value of (increase or decrease?for every iteration to know whether the array is sortedwe need to scan the full list we also know that number of sub lists we get are equal to the value of so if we decide to reduce the value of after every iteration we will reduce the number of sub lists also in every iteration eventuallywhen will be set to we will have only one sub list hence we know the termination condition for our algorithm is since for every iteration we are decreasing the value of the increment (kthe algorithm is also known as "diminishing increment sortany sorting algorithm or combination of algorithms can be used for sorting the sub listse some shell sort implementation use bubble sort for the last iteration and insertion sort for other iterations we use insertion sort in this tutorial how does shell sort give better performance if the sorting is ultimately done by algorithms like insertion sort and bubble sortthe rationale is as follows if the list is either small or almost sorted then insertion sort is efficient since less number of elements will be shifting in shell sort as we have already seenthe original list is divided into smaller lists based on the value of increment and sorted initially value of is fairly large giving large number of small sub lists we know that simple sorting algorithms like insertion sort are effective for small listssince the data movements are over short distances as reduces in valuethe length of the sub lists increases but since the earlier sub lists have been sortedwe except the full list to look more and more sorted again note that algorithms such as insertion sort are fairly efficient when they work with nearly sorted lists thus the inefficiency arising out of working with larger lists is partly compensated by lists being increasingly sorted this is the intuitive explanation for the performance of shell sort how to choose the value of increment ktill date there is no convincing answer to what should be the optimal sequence for the incrementk but it has been empirically found that larger number of increments gives more efficient results also it is advisable not to use empirical sequences like , , , or , , , if we do sofor different iterationwe may get almost the same elements in the sub lists to compare and sort which will not result in better performance for exampleconsider list and increment sequences and when the increment is you will get the following sub lists ( , ( , ( , ( , ( lovely professional university