Shell Sort

Shell sort is a sorting algorithm that is a generalization of insertion sort, with two observations:
insertion sort is efficient if the input is "almost sorted", and insertion sort is typically inefficient because it moves values just one position at a time.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 

Reference:http://en.wikipedia.org/wiki/Shell_sort

http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/shell/shellen.htm