Insertion sort, merge sort and quicksort on doubly$-$linked list

Outline: in this assignment you will implement insertion sort, mergesort and quicksort on a doubly$-$

linked list. You must use the std::list data structure to hold the elements to be sorted $($do not

provide your own linked list implementation$).$ In addition to the sorting algorithms, you should provide a

main with timing experiments to compare the performance of your sorting algorithms on different

inputs $($lists in sorted order, in reverse$-$sorted order, with random elements, or all duplicate elements$).$

You should make use of iterators in your code. For example, in the $$merge$$ function of mergesort you

can use an iterator to the left sub$-$list and a second iterator the right sub$-$list, and advance the iterator of

the appropriate sub$-$list when it$$s current element is added to the merged list.

You should also provide an efficient and generic solution through use of templates and move$/$swap

semantics. Your sorting algorithms should work on lists of any type, and should avoid copying elements

whenever it is possible to move.

Extra marks will be given for clever use of iterators, for efficient solutions $($both in time and space

complexity$)$ and for detailed timing experiments in main. Write some comments at the top of your

source code describing the overall results of your timing experiments.