Optimized Merge Algorithm for Merge Sort.

Home           Algorithms Home

   Here I have tried to reduce memory comsumption by using a queue instead of a temprary
   array, and also, I have scrapped the idea of getting the sorted stuff in the temporary
   memory. Instead, I traverse the original array checking for array elements that are
   out of their place, and put it in the queue, so that they can be put in their proper place
   when the time comes. This means that the maximum value of the queue should never exceed
   half the size of the array passed to merge for merging, but on an average, I still have
   to perform some tests for random data to find its average size, which should never become
   half the size of the array unless in the worst case when all the elements of the 2nd half
   of the array exceed the elements of the first half. The best case is when the data is already
   sorted, when absolutely no memory is used.

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);


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)
{

  queue<int> q;  //using a queue instead of a temporary array.
  int mid = (first + last) / 2;

  int i = first;
  int j = mid + 1;


  while ((j <= last) && (i <= mid))
    {
      if (!q.empty ())
    {
      if ((data_to_merge[j] < data_to_merge[i]) && (data_to_merge[j] < q.front ()))
        {
          q.push (data_to_merge[i]);
          data_to_merge[i++] = data_to_merge[j++];
        }
      else if ((q.front () < data_to_merge[i]) && (q.front () < data_to_merge[j]))
        {
          q.push (data_to_merge[i]);
          data_to_merge[i++] = q.front ();
          q.pop ();
        }
      else i++;
    }

      else
    {
      if (data_to_merge[j] < data_to_merge[i])
        {
          q.push (data_to_merge[i]);
          data_to_merge[i++] = data_to_merge[j++];
        }
      else i++;

    }
    }


  if (i == mid)
    {
      if (!q.empty ())  //redundant check!!!, but I need ur opinion on it, cause I'm not too sure.
    {
      if (q.front () < data_to_merge[i])
        {
          q.push (data_to_merge[i]);
          data_to_merge[i++] = q.front ();
          q.pop ();
        }
      else i++;
    }
    }


      while ((j <= last) && (!q.empty ()))
    {
      if (q.front () > data_to_merge[j])
        {
          data_to_merge[i++] = data_to_merge[j++];
        }
      else
        {
          data_to_merge[i++] = q.front ();
          q.pop ();
        }
    }


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

    while (!q.empty ())
      {
    data_to_merge[i++] = q.front ();
    q.pop ();
      }

}


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