Project: Insertion Sort
The [[Insertion sort]] is almost as easy to implment as the bubble sort and has similar performance characteristics. Write a function that takes a list of integers and sorts the list without modifying it, returning a sorted list, using an insertion sort. Test the function by creating a random list of integers, print the random list, sort the list, then print out the sorted list. Accept the number of integers to put in the list and the maximum integer to randomly generate on the command line. What is the worst case performance of the Insertion sort?