## 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?

## Output

$

**g++ -std=c++17 InsertionSort.cpp -o InsertionSort -lfmt**$**./InsertionSort 10 10**Random List [6, 4, 0, 8, 8, 0, 3, 7, 0, 4] Sorted List [0, 0, 0, 3, 4, 4, 6, 7, 8, 8] $**g++ -std=c++17 InsertionSort.cpp -o InsertionSort -lfmt**$**./InsertionSort 20 100**Random List [63, 61, 77, 32, 41, 25, 37, 42, 71, 42, 66, 31, 45, 24, 71, 37, 99, 26, 32, 20] Sorted List [20, 24, 25, 26, 31, 32, 32, 37, 37, 41, 42, 42, 45, 61, 63, 66, 71, 71, 77, 99]