# Sorting Homework

### Shellsort

Shellsort is an in-place comparison sort published by American mathematician and engineer Donald Lewis Shell in 1959. It extends another sorting algorithm, insertion sort in this case, allowing it to compare elements that are far apart.

Given a sequence of "gap values" or "h values", each pass of ShellSort considers only every h elements in the list and sorts these relative to one another.

As long as the sequence of h values ends in 1, the last pass will be a regular insertion sort.

While Shellsort requires more operations than quicksort, it is preferred over quicksort in some embedded or otherwise constrained environments.

1. Implement Shellsort using an inner insertion sort like in the pseudocode below. Use Tokuda's sequence as gap values. A worked example and more in-depth description of the algorithm is available on Wikipedia s.v. Shellsort.

1. For an unsorted list of size n, select the largest value in the Tokada sequence < n
2. For each value, h, in the Tokada sequence from this value down to 1:
a. For each position in the list from h up to the length of the list minus one
i.   save the value in the current position to a temporary variable
ii.  clear the value stored at the current position
iii. move backward through the array in steps of size h given
that your index in the list is >= h and the next value you would
encounter while doing this is greater than the value saved in temp
* Write this next value to the current location
# This moves elements in the gap sequence that are already sorted
# up to make room for the element currently being sorted
iv.  once your index in the list is < h or the next value you would
encounter is less than or equal to the value saved in temp
* Write the value in temp to the current location

2. If one exists, describe a dataset for which insertion sort would outperform this implementation of Shellsort. If one does not exist, explain why.

3. If one exists, describe a dataset for which insertion sort would underperform this implementation of Shellsort. If one does not exist, explain why.
4. Implement insertion sort as described in Skiena ยง4.3.5 and time its performance compared to your implementation of Shellsort over the dataset(s) you described in the two previous questions. Include your code with your submission.
5. Describe your findings from the comparison.

### Library sort methods

1. Python has more than one built-in method for sorting. What are they and how do they differ?