Rewrite the following MergeSort so that instead of using vectors, it will instea

ID: 3861820 • Letter: R

Question

Rewrite the following MergeSort so that instead of using vectors, it will instead use the class List. Each function must be edited so that they can use a List. Generic functions may not be used, such as sort(), inplace_merge(), merge() or copy(). And it should not contain Nodes.

#include <iostream>
#include <vector>
#include <iterator>

using namespace std;

template<class Itr>
void inplaceMerge(Itr low, Itr mid, Itr high)
{
   int dist = high - low;
   vector<typename iterator_traits<Itr>::value_type> temp(dist);
   Itr i = low;
   Itr j = mid;
   Itr k = temp.begin();

   while (i < mid && j < high)
       if (*i < *j)
           *k++ = *i++;
       else
           *k++ = *j++;
   while (i < mid)
       *k++ = *i++;
   while (j < high)
       *k++ = *j++;

   for (k = temp.begin(), i = low; k != temp.end(); k++, i++)
       *i = *k;
} // inplaceMerge

template <class Itr>
void m_sort(Itr start, unsigned int low, unsigned int high)
{
   if (low + 1 < high) {
       unsigned int center = (low + high) / 2;
       m_sort(start, low, center);
       m_sort(start, center, high);
       inplaceMerge(start+low, start+center, start+high);
   }
} // m_sort

template <class T>
void mergeSort(vector<T> & s)
{
m_sort(s.begin(), 0, s.size());
} // mergeSort

main()
{
vector<int> v;
int temp;

while (cin >> temp)
v.push_back(temp);

mergeSort(v);

   for (int i = 0; i < v.size(); i++)
       cout << v[i] << ' ';
   cout << endl;
} // main

Explanation / Answer