swap swap swap sifting is done notes this approach writes sifted element to temporary position many times next implementation eliminates those unnecessary writes shifting instead of swapping we can modify previous algorithmso it will write sifted element only to the final correct position let us see an illustration swap swap swap sifting is done insert to final position it is the most commonly used modification of the insertion sort using binary search it is reasonable to use binary search algorithm to find proper place for insertion this variant of the insertion sort is called binary insertion sort after position for insertion is foundalgorithm shifts the part of the array and inserts the element this version has lower number of comparisonsbut overall average complexity remains ( from practical point of view this improvement is not very importantbecause insertion sort is used on quite small data sets complexity analysis insertion sort' overall complexity is ( on averageregardless of the method of insertion on the almost sorted arrays insertion sort shows better performanceup to (nin case of applying insertion sort to sorted array number of writes is ( on averagebut number of comparisons may vary depending on the insertion algorithm it is ( when shifting or swapping methods are used and ( log nfor binary insertion sort from the point of view of practical applicationan average complexity of the insertion sort is not so important as it was mentioned aboveinsertion sort is applied to quite small data sets (from to elements shell sort most of the sorting algorithms seen so far such as insertion sort and selection sort have run time complexity of ( we also know that no sorting algorithm can have time complexity less than ( )since we need to scan the list at least once for exampleinsertion sort best case complexity is (ncan we get better performance and get run time complexity between ( and ( )the answer is yes and there are many algorithms with complexity in this rangewith varying tradeoffs in this notewe describe one approachshell sort shell sort has evolved as trial and error algorithm analytical results are not available but empirically it has been found that the lovely professional university