Implement Insertion Sort

In this assignment series we will explore a number of sorting algorithms. Your goal is to understand both the implementation of the algorithm, and the circumstances under which it is a good choice.

Tasks

Read about the Insertion Sort

When you’re ready, create a new branch for your data-structures repository and add a module to implement the sorting algorithm. Your sorting function should only take in a list of values and return a sorted list of those same values. Otherwise, the implementation details are up to you.

Include tests that demonstrate that your sort works correctly.

Include an “if __name__ == ‘__main__’:” block at the end of your module that demonstrates the performance characteristics of this sort. Cover a variety of lengths of input in the best-case, worst-case, and average-case scenarios. Executing your module should print informative output about the performance of your sort to the terminal. So, for example, if you were writing the “Bogo Sort” algorithm:

$ python bogosort.py # running from the command line

# output
The bogosort randomly shuffles the items in a list until the list is sorted.
It performs best for very short lists

Input: [2, 1]
    number of runs: 500
    average time: 2.0e-4 seconds

Input: [randint(0, 1000000) for i in range(10000)]
    number of runs: 500
    average time: 2345.6 seconds

Add tests to demonstrate that the sorting algorithm works in both Python 2 and 3

Add information about your implementation to the README.md in your package, including any sources and collaborations you used in creating it.

Include the time complexity of your implementation of this sort algorithm in your README.

Submitting Your Work

When your work is complete and your tests are passing, create a pull request from your working branch back to master. Submit the URL of your pull request. When you’ve done this, you may merge your pull request, but do not delete your branch until your work has been graded.

Use the comment feature to add any questions, comments or reflections on your work.