In the given skeleton code, implement the following:

$1.$ Implement insertion sort in the insertion sort function. This functions takes in an unsorted sequence

given in $[$first$,$ last$)$ and sorts them using insertion sort approach.

$2.$ Implement the traditional merge operation in the merge function. This functions takes in two sorted

sequences $[$first$,$ mid$)$ and $[$mid$,$ last$)$ and merges them into a single sequence contained in $[$first$,$ last$).$

$3.$ Implement the merge operation of $$n$/$k$$ subsequences in the merge k function. This functions takes

in $$n$/$k$$ sorted sequences defined in $[$first$,$ last$)$ and merges them into a single sequence contained in

$[$first$,$ last$).$ Here the input k is the size of each sub$-$sequence excluding the last which might be smaller

than k$.$

$4.$ Implement merge sort algorithm as stated above in the merge sort function.

Skeleton Code be#ifndef $\_$SORT$\_$H$\_$

#define $\_$SORT$\_$H$\_$

#include

#include

namespace my$\_$algorithm$\{$

$////////////////////////////////////////////////////////////////////////////////$

$///$ @brief Swap values of two elements

$///$ @tparam T Value type

$///$ @param a First value

$///$ @param b Second value

template

void swap$($T& a$,$ T& b$)\{$

T tmp $=$ a;

a $=$ b;

b $=$ tmp;

$\}$

$////////////////////////////////////////////////////////////////////////////////$

$///$ @brief Sort the range $[$first$,$ last$)$ into nondecreasing order

$///$ @tparam RandomAccessIterator Random Access Iterator

$///$ @tparam Compare Comparator function

$///$ @param first Initial position of sequence to be sorted

$///$ @param last Final position of sequence to be sorted

$///$ @param comp Binary function that accepts two elements in the range as

$///$ arguments and returns a value convertable to bool. The value

$///$ returned indicates whether the element passed as first argument

$///$ is considered to go before the second in the ordering it

$///$ defines.

$///$

$///$ Bubble Sort $-$ Example

template

void bubble$\_$sort$($RandomAccessIterator first, RandomAccessIterator last,

Compare comp$)\{$

$//$ Traverse from left to right for each ith largest element positioning

for$($RandomAccessIterator i $=$ first; i $!=$ last; $++$i$)$

$//$ Compare each element with its right neighbor to bubble up ith largest element

for$($RandomAccessIterator j $=$ first; j$+1!=$ last; $++$j$)$

if$($comp$(*($j$+1),*$j$))//$ Compare j with its right neighbor

swap$(*($j$+1),*$j$)$; $//$ Swap if neighbor is smaller

$\}$

$////////////////////////////////////////////////////////////////////$

$///$ @brief Your implementation of insertion selection sort

$///$ @tparam RandomAccessIterator Random Access Iterator

$///$ @tparam Compare Comparator function

$///$ @param first Initial position of sequence to be sorted

$///$ @param last Final position of sequence to be sorted

$///$ @param comp Binary function that accepts two elements in the range as

$///$ arguments and returns a value convertable to bool. The value

$///$ returned indicates whether the element passed as first argument

$///$ is considered to go before the second in the ordering it

$///$ defines.

template

void insertion$\_$sort$($RandomAccessIterator first, RandomAccessIterator last, Comparator comp$)\{$

$///$ @TODO

int i$,$ key, j;

for $($i $=1$; i $<$ n; i$++)\{$

key $=$ RandomAccessIterator$[$i$]$;

j $=$ i$-1$;

while $($j $>0$ && RandomAccessIterator$[$j$]>$ key$)\{$

RandomAccessIterator$[$j$+1]=$ RandomAccessIterator $[$j$]$;

j $=$ j$-1$;

$\}$

arr$[$j$+1]=$ key;

$\}$

$\}$

$////////////////////////////////////////////////////////////////////$

$///$ @brief Your implementation of merging two sorted sequences

$///$ @tparam RandomAccessIterator Random Access Iterator

$///$ @tparam Compare Comparator function

$///$ @param first Initial position of the first sequence to be merged

$///$ @param mid Initial position of the second sequence to be merged

$///$ @param last Final position of the second sequence to be merged

$///$ @param comp Binary function that accepts two elements in the range as

$///$ arguments and returns a value convertable to bool. The value

$///$ returned indicates whether the element passed as first argument

$///$ is considered to go before the second in the ordering it

$///$ defines.

template

void merge$($RandomAccessIterator first, RandomAccessIterator mid, RandomAccessIterator last, Comparator comp$)\{$

$///$ Hint: To allocate external memory to store merging of result use

$///$ std::vector

$///$ Remember to copy back the merged result

$///$ @TODO

$\}$

$////////////////////////////////////////////////////////////////////$

$///$ @brief Your implementation of merging n$/$k sorted sequences of size k

$///$ @tparam Randomlow: