Insertion sort is an algorithm for sorting an array of values into ascending order. It works by using two loops, an outer loop that scans the data once, and an inner loop that scans from position of the outer loop counter to the start of the array, looking for a suitable spot to place the current element being sorted. Insertion sort has (2) running time, unless the input is already sorted, in which case the running time is ().

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

Step 1: create your own doubly-linked list class or check in c++.

Step 2: implement insertion sort using Linked List as input. Like this:

template LinkedList& insertionSort(LinkedList& theList) { 

 //returns a sorted 

INSERTION-SORT(A) 1 for j - 2 to length[A] 2 do key + A[j] 3 Insert A[j] into the sorted sequence A[1.. j - 1]. 4 ir j - 1 5 while i > 0 and A[i] > key 6 do A[i+1] + A[i] 7 iti - 1 8 A[i+1] + key