How do I interface a merge_sort algorithm to Vector and a user defined dynamic_array? - to_do
<p>I want to take this merge_sort I wrote and put it into a class.  Because their is some coupling of the variables, particularly - left, right_begin, right...I want to make these class members.  The variables that are local to each function I will leave as local function variables.</p>

<p>Also this function will be used for another class I have called dynamic_array which is a bit more efficient than vector.  However I want to make it available to the STL vector as well.</p>

<p>How do I do this.  Do I use inheritance?  Do I make the class a composite class of my dynamic_array...If I do this it will not be available to vector though.</p>

<p>The Question:
How do I make my merge_sort class interface with the STL container Vector and to my own container dynamic_array.</p>

<p>This is for an interview preparation.</p>

<p>Thank you.  Dynamic Array code below(remove old merge_sort cold)</p>

<p>Merge Sort Code - to be converted to a class</p>

<pre><code>#include &lt;iostream&gt;
using namespace std;
const int size=8;
int scratch[size],array[size]={6,5,3,1,8,7,2,4};
void print_array(int arr[]){ for (int i = 0; i &lt; size; i++) cout &lt;&lt; arr[i] &lt;&lt; endl;}
void flip_if_unordered(int &amp;x, int &amp;y)
  {
  if(array[x]&gt;array[y])
    {
    int tmp = array[x];
    array[x] = array[y];
    array[y] = tmp;
    }
  }
void merge_algo(int &amp;left, int &amp;right_begin, int &amp;right)
  {
  int iter,iter_left=left,iter_right=right_begin;  
  for(iter=left;iter&lt;=right;++iter)
    {
    if( (iter_right&gt;right) || ((iter_left &lt; right_begin) &amp;&amp; (array[iter_left]&lt;=array[iter_right])))
      {
      scratch[iter]=array[iter_left];
      ++iter_left;
      }
    else
      {
      scratch[iter]=array[iter_right];
      ++iter_right;
      }
    }
  for(iter=left;iter&lt;=right;++iter){array[iter]=scratch[iter];}
  }
void merge_recurse(int left,int right)
  {
  int left_end=(left+((right-left)/2)); 
  int right_begin=left_end+1;  
  if(((left+1)==right)){flip_if_unordered(left,right);return;}
  else if ((left==right)){return;}
  else
    { 
    merge_recurse(left,left_end);               
    merge_recurse(right_begin,right);  
    merge_algo(left,right_begin,right);
    }   
  }
int main()
  {
  merge_recurse(0,(size-1)); 
  print_array(array);
  return 0;
  }
</code></pre>

<p>Dynamic Array</p>

<pre><code>#include "c_arclib.cpp"
using namespace std;
template &lt;class T&gt; class dynamic_array
  {
  private:
    T* array;
    T* scratch;
    void merge_recurse(int left, int right)
      {
      if(right == left + 1)
        {
        return;
        }
      else
        {
        int i = 0;
        int length = right-left;
        int midpoint_distance = length/2;
        int l = left, r = left + midpoint_distance;
        merge_recurse(left, left + midpoint_distance);
        merge_recurse(left + midpoint_distance, right);
        for(i = 0; i &lt; length; i++)
          {
          if((l &lt; (left + midpoint_distance)) &amp;&amp; (r == right || array[l] &gt; array[r]))
            {
            scratch[i] = array[l];
            l++;
            }
          else
            {
            scratch[i] = array[r];
            r++;
            }
          }
        for(i = left; i &lt; right; i++)
          {
          array[i] = scratch[i - left];
          }
        }
      }
    void quick_recurse(int left, int right) 
      {  
      int l = left, r = right, tmp;
      int pivot = array[(left + right) / 2];
      while (l &lt;= r)
        {
        while (array[l] &lt; pivot)l++;
        while (array[r] &gt; pivot)r--;
        if (l &lt;= r) 
          {
          tmp = array[l];
          array[l] = array[r];
          array[r] = tmp;
          l++;
          r--;
          }
        }
      if (left &lt; r)quick_recurse(left, r);
      if (l &lt; right)quick_recurse(l, right);
      }  
  public:
    int size;
    void rorder();
    void order();
    void randorder();
    dynamic_array(int sizein)
      {
      size=sizein;
      array=new T[size]();
      }
    void print_operator(std::ostream &amp;os = cout) const
      { 
      for (int i = 0; i &lt; size; i++) os &lt;&lt; array[i] &lt;&lt; endl; 
      } 
    int merge_sort()
      {
      scratch = new T[size]();
      if(scratch != NULL)
        {
        merge_recurse(0, size);return 1;
        }
      else{return 0;}
      }
    void quick_sort()
      {
      quick_recurse(0,size);
      }
  };
template &lt;class T&gt; void dynamic_array&lt;T&gt;::randorder()
  {
  srand(time(NULL));
  int *ap;
  for(ap=array;ap!=array+size;++ap){*ap=rand();} 
  }
template &lt;class T&gt; void dynamic_array&lt;T&gt;::order()
  {
  int *ap,i=0;
  for(ap=array;ap!=array+size;++ap)                                             
    { 
    *ap=i;
    ++i;        
    } 
  }
template &lt;class T&gt; void dynamic_array&lt;T&gt;::rorder()
  {
  int *ap,i=size;
  for(ap=array;ap!=array+size;++ap)                                             
    { 
    *ap=i;
    --i;        
    } 
  }
template&lt;class T&gt; ostream&amp; operator&lt;&lt;(ostream&amp; stream, dynamic_array&lt;T&gt; const&amp; data) 
  { 
  data.print_operator(stream);
  return stream; 
  }   
int main()
  {
  dynamic_array&lt;int&gt; d1(10);
  d1.order();
  cout &lt;&lt; d1;
  /*
  clock_t time_start=clock();
  d1.merge_sort(); 
  clock_t time_end=clock();
  double result = (double)(time_end - time_start) / CLOCKS_PER_SEC; 
  cout &lt;&lt; result;
  cout &lt;&lt; d1;
  */
  }
</code></pre>
