• Shell sort
  

Definition:

Invented by Donald Shell in 1959. It improves upon bubble sort and insertion sort by moving out of order elements more than one position at a time.
It 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.

Run-time Complexity Analysis:
♥ This is an effective in terms of the efficiency of the sorted list.

Codes:
input: an array a of length n

inc ← round(n/2)
while inc > 0 do:
for i = inc .. n − 1 do:
temp ← a[i]
j ← i
while j ≥ inc and a[j − inc] > temp do:
a[j] ← a[j − inc]
j ← j − inc
a[j] ← temp
inc ← round(inc / 2.2)

Application:
♥ Sorting the numbers in a certain row.

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