Divide And Conquer

Merge Sort:

void Merge(int list[], int lowIndex, int highIndex, int midIndex)
{
   int *tempList = new int[highIndex-lowIndex+1];
   int firstLow = lowIndex;
   int secondLow = midIndex + 1;
   int index = 0;
   while(firstLow <= midIndex && secondLow <= highIndex)
   {
      if (list[firstLow] < list[secondLow])
         tempList[index++] = list[firstLow++];
      else
         tempList[index++] = list[secondLow++];
   }

   while (firstLow <= midIndex)
   {
      tempList[index++] = list[firstLow++];
   }

   while (secondLow <= highIndex)
   {
      tempList[index++] = list[secondLow++];
   }

   for (int ii = 0; ii < index; ii++)
   {
      list[lowIndex+ii] = tempList[ii];
   }
   delete[] tempList;
}

void MergeSort(int list[], int lowIndex, int highIndex)
{
   if (lowIndex < highIndex)
   {
      int midIndex = lowIndex + (highIndex-lowIndex)/2;
      MergeSort(list, lowIndex, midIndex);
      MergeSort(list, midIndex+1, highIndex);
      Merge(list, lowIndex, highIndex, midIndex);
   }
}

Leave a Reply

Your email address will not be published. Required fields are marked *