Insertion sort is a simple sorting algorithm: a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages:


              ex: repetition of insertion sort removes an element from the input data, inserting it into the correct position in the already-sorted list, until no input elements remain. The choice of which element to remove from the input is arbitrary, and can be made using almost any choice algorithm.




Shellsort- is one of the oldest sorting algorithms, named after its inventor D.L. Shell (1959) [She 59]. It is fast, easy to understand and easy to implement. However, its complexity analysis is a little more sophisticated.

Ex:

Let  3 7 9 0 5 1 6 8 4 2 0 6 1 5 7 3 4 9 8 2  be the data sequence to be sorted. First, it is arranged in an array with 7 columns (left), then the columns are sorted (right):

3 7 9 0 5 1 6 8 4 2 0 6 1 5 7 3 4 9 8 2

3 3 2 0 5 1 5 7 4 4 0 6 1 6 8 7 9 9 8 2