# Algorithm Implementation/Sorting/Shell sort

## CEdit

``` /* Performs an insertion sort on elements of a[] with the given gap.
* If gap == 1, performs an ordinary insertion sort.
* If gap >= length, does nothing.
*/
void shellSortPhase(int a[], int length, int gap) {
int i;
for (i = gap; i < length; ++i) {
int value = a[i];
int j;
for (j = i - gap; j >= 0 && a[j] > value; j -= gap) {
a[j + gap] = a[j];
}
a[j + gap] = value;
}
}//end
void shellSort(int a[], size_t length) {
/*
* gaps[] should approximate a [[w:geometric progression|geometric progression]].
* The following sequence is the best known in terms of
* the average number of key comparisons made [http://www.research.att.com/~njas/sequences/A102549]
*/
static const int gaps[] = {
1, 4, 10, 23, 57, 132, 301, 701
};
int sizeIndex;

for (sizeIndex = sizeof(gaps)/sizeof(gaps[0]) - 1;
sizeIndex >= 0;
--sizeIndex)
shellSortPhase(a, length, gaps[sizeIndex]);
}
```

```import Data.List (transpose, insert, unfoldr)

-- Insertion sort, for sorting columns.
insertionSort :: Ord a => [a] -> [a]
insertionSort = foldr insert []

-- Splits a list into k columns.
columnize :: Int -> [a] -> [[a]]
columnize k = transpose . takeWhile (not . null) . unfoldr (Just . splitAt k)

-- Merges columns back into a single list.
decolumnize :: [[a]] -> [a]
decolumnize = concat . transpose

-- Each phase of the Shell sort breaks the list into k columns, sorts each with an
-- insertion sort, then merges those columns back into a list.
shellSortPhase :: (Ord a) => Int -> [a] -> [a]
shellSortPhase k = decolumnize . map insertionSort . columnize k

-- The full Shell sort, applying phases with arbitrarily large gap sizes according to
-- R. Sedgewick, J. Algorithms 7 (1986), 159-173
shellSort :: (Ord a) => [a] -> [a]
shellSort xs = foldr shellSortPhase xs gaps
where gaps = takeWhile (< length xs) sedgewick
sedgewick = concat [[9 * 2^n - 9 * 2^(n `div` 2) + 1,
8 * 2^(n+1) - 6 * 2^(n `div` 2) + 1] | n <- [0..]]
```

## JavaEdit

```/** Shell sort using Shell's (original) gap sequence: n/2, n/4, ..., 1. */
public static <T extends Comparable<? super T>> void shellSort(T[] array) {
// loop over the gaps
for (int gap = array.length / 2; gap > 0; gap /= 2) {
// do the insertion sort
for (int i = gap; i < array.length; i++) {
T val = array[i];
int j;
for (j = i; j >= gap && array[j - gap].compareTo(val) > 0; j -= gap) {
array[j] = array[j - gap];
}
array[j] = val;
}
}
}
```

## RubyEdit

```module ShellSort
def self.sort(keys)
sort!(keys.clone)
end

def self.sort!(keys)
gap = keys.size/2
while gap > 0
for j in gap...keys.size
key = keys[j]
i = j
while (i >= gap and keys[i-gap] > key)
keys[i] = keys[i-gap]
i -= gap
end
keys[i] = key
end
gap /= 2
end
keys
end
end
```

## PythonEdit

``` def shellSort(array):
"Shell sort using Shell's (original) gap sequence: n/2, n/4, ..., 1."
gap = len(array) // 2
# loop over the gaps
while gap > 0:
# do the insertion sort
for i in range(gap, len(array)):
val = array[i]
j = i
while j >= gap and array[j - gap] > val:
array[j] = array[j - gap]
j -= gap
array[j] = val
gap //= 2
```