Merge Sort (traditional implementation)

Home           Algorithms Home

This is the traditional implementational of the Merge Sort, and Merge algorithm requited by it.


You can copy the code between the 2 HORIZONTAL LINES, paste it and save it as ASCII test, and compile it with a standards compliant C++ compiler such as g++.

void rec_merge_sort (int* data, int first, int last);
void merge_sort (int* data, int size);
void merge_data (int* data_to_merge, const int first, const int last);
int* int_cpy_n (int* dest, const int* src, int size);


int* int_cpy_n (int* dest, const int* src, int size)  /*here, no checks are performed for any
                          stuipid array bounds.*/
{
  return (reinterpret_cast<int*>(memcpy (reinterpret_cast<void*>(dest),
                   reinterpret_cast<const void*>(src),
                 static_cast<size_t>(size * sizeof (int)))));
  return (dest);

}
/*memcpy copys only non-overlaping memory, to copy overlaping memory, use memmove.*/



void rec_merge_sort (int* data, int first, int last)
{
  if (first < last)
    {
      int mid = (first + last) / 2;
      rec_merge_sort (data, first, mid);
      rec_merge_sort (data, (mid + 1), last);
      merge_data (data, first, last);  //assume mid = (first + last) / 2. *it is redundant here......*
    }
}



void merge_data (int* data_to_merge, const int first, const int last)
{
  int* temp = new int[last - first + 1];

  int mid = (first + last) / 2;
  int i = first;
  int i1 = 0;
  int j = mid + 1;


  while ((i <= mid) && (j <= last))
    {
      if (data_to_merge[i] > data_to_merge[j])
    {
      temp[i1++] = data_to_merge[j++];
    }
      else
    {
      temp[i1++] = data_to_merge[i++];
    }
    }


    while (i <= mid)
      temp[i1++] = data_to_merge[i++];


    while (j <= last)
      temp[i1++] = data_to_merge[j++];

    int_cpy_n ((data_to_merge + first), temp, i1);

    delete[] temp;

}


void merge_sort (int* data, int size)
{
  rec_merge_sort (data, 0, (size-1));
}



int main ()
{
  int a[] = {-53,-123,-12,10,9,8,7,6,5,4,3,2,1,0};
  merge_sort (a,14);

  for (int i = 0; i<14; i++)
 {
    std::cout<<a[i]<<" ";
  }

 std::cout<<std::endl;
  return (0);
}









Hosted by www.Geocities.ws

1