#ifndef $\_$SORTER$\_$H

#define $\_$SORTER$\_$H

#include

#include

#include

using namespace std;

template

void sorter$($vector &vec, int k$)\{$

$//$ write your solution for k$-$way merge sort below

$\}$

#endif

Instructions:

K$-$Way Merge Sort: Implementation details and hints

The input array will be in the form of a vector. The signature of the function you will implement is given below:

template

void sorter$($vector &vec, int k$)$;

For this project your sorting code should go in the file sorter.h$,$ because we want you to implement a sorting function template to be able to sort vectors of any data type as long as the comparison operator, $<,$ is defined for that type.

In order to be able to call this function recursively, you need to create k new vectors inside the function and call sorter on them. After the smaller vectors are sorted, you need to merge all k of them and store the sorted values back on your input vector, vec.

Splitting k ways

In the first part of your function, you need to make k new vectors containing roughly n$/$k elements $($where n is the size of the original input vector$).$ You probably want to store these in another vector $($a vector of vectors$).$ There are many ways to achieve this splitting step. Two approaches are outlined below.

In the first approach, use math to decide how big each of the new vectors need to be$.$ Note that, unless n is some multiple of k$,$ performing the integer division n$/$k will yield a truncated result. E$.$g$.,$ suppose n $=11$ and k $=3$: the truncated result for $11/3$ is $3.$ However, if we create $3$ vectors of size $3,$ we leave out $2$ elements! So our vectors should be sizes $4,4,$ and $3.$ Note, though, we can easily figure out how many vectors need an additional element by using the modulo operator: $11\%3=2.$

In the second approach, we use a "round$-$robin" approach to assign elements to our collection of vectors. In this approach, simply loop over all of the elements in the original input vector; the first element should go in the first of your k vectors, the next in the second vector, and so forth. You can easily keep track of where you are in the k vectors and properly "wrap around" back to the start using modulo math: x $\%$ k $($for integer x$)$ always returns a value between $0$ and k $-1.$

k$-$way merge

There are a number of ways you can implement the merging of k smaller sorted vectors. Two approaches are outlined below. Note: for this project we are not implementing k$-$way merge in the most efficient fashion. This is intentional. You may find more efficient methods described online $-$ do not use these! For the next analysis project, you will be analyzing k$-$way merge as described for this project, and performing timing experiments. If you implement a more efficient algorithm, you will be unable to collect the desired results for the analysis project.

Approach $1$

Approach $1$: minimum elements first

One way is to keep k different indices $($e$.$g$.,$ in a vector$)$ to keep track of where you are in each of the sorted vectors during the merge operation.