Typically, an array of unsorted values is the input to insertion sort. In this assignment, you will implement the insertion sort algorithm on a doubly-linked list (instead of an array).

A doubly-linked list is just a linked list where each node in the list has both a pointer to the next node and a pointer to the previous node. The first node in the list has a nullptr to its previous node. The last node in the list has a nullptr to its next node.

Step 1: create your own doubly-linked list class or check lecture 7 (code taken from Weiss textbook) on how to create one in C++. You may use the implementation from lecture 7, if you want.

Step 2: implement insertion sort using Linked List as input. The function signature should look something like this: template

Linkedlist& InsertionSort(Linkedlist& (Thelist) {

//your code here, eventually returns a sorted

}

Note the use of pass-by-reference and the use of templates. Do not simply convert the LinkedList to an array, sort using an array, and then convert it back! You must sort the LinkedList directly, otherwise the exercise loses its value. The purpose of the assignment is to get familiar with pointer manipulation and linked list operations.

In your main, you should initialize a linked list and use a for loop combined with a random number generator to fill it with some random elements. Print the initial random list to display the elements. Then, pass your list to the insertionSort method (as above) and when the sorting completes, print the result to display the sorted elements.

Part 2: Re-code insertion sort using C++s vector class instead of a linked list as the underlying container (vector is basically a fancy version of array). Compare the running time (vector vs linked list) using the chrono library. Which implementation takes longer (linked list or vector)? Why? Write a small paragraph comment at the top of your main explaining why you got the result you got when you timed the two implementations. Discuss time complexity.