This sort is a simple extension of Insertion sort. Its speed comes from the fact that it exchanges elements that are far apart the insertion sort interchange only adjacent elements. Shell sort is also called as diminishing increment sort or gap sort or comb sort developed by Donald Shell. The shell sort is base on most already sorted array elements. The process first divides the array into smaller parts, which are then separated sorted using the insertion sort.
Assume that x array hold 8 elements as follows : x[8]
0 1 2 3 4 5 6 7
79 36 89 12 23 59 31 18
