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 (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 in c++

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