natalie_code/mergesort.cpp

// Merge Sort
//
// Author: Rob Gysel
// ECS60, UC Davis
// Adapted from: Lysecky & Vahid "Data Structures Essentials", zyBooks

#include "mergesort.h"
#include <iostream>
#include <cstdio>

int* MergeSort(std::vector<int>* numbers) {
  int comparisonCounter = 0;
  int memAccessCounter = 0;
  static int returnCounters[2];

  MergeSortRecurse(numbers, 0, numbers->size() - 1, &comparisonCounter, &memAccessCounter);
  memAccessCounter++;

  returnCounters[0] = comparisonCounter;
  returnCounters[1] = memAccessCounter;
  return returnCounters;
}


void MergeSortRecurse(std::vector<int>* numbers, int i, int k, int *comparisonCounter, int *memAccessCounter) {
   int j = 0;

   if (i < k) {
      j = (i + k) / 2;  // Find the midpoint in the partition

      // Recursively sort left and right partitions
      MergeSortRecurse(numbers, i, j, comparisonCounter, memAccessCounter);
      *memAccessCounter = *memAccessCounter + 1;
      MergeSortRecurse(numbers, j + 1, k, comparisonCounter, memAccessCounter);
      *memAccessCounter = *memAccessCounter + 1;

      // Merge left and right partition in sorted order
      Merge(numbers, i, j, k, comparisonCounter, memAccessCounter);
      *memAccessCounter = *memAccessCounter + 1;
   }
}

void Merge(std::vector<int>* numbers, int i, int j, int k, int *comparisonCounter, int *memAccessCounter) {
   int mergedSize = k - i + 1;                // Size of merged partition
   int mergePos = 0;                          // Position to insert merged number
   int leftPos = 0;                           // Position of elements in left partition
   int rightPos = 0;                          // Position of elements in right partition
   std::vector<int> mergedNumbers;
   mergedNumbers.resize(mergedSize);          // Dynamically allocates temporary array
                                              // for merged numbers

   leftPos = i;                               // Initialize left partition position
   rightPos = j + 1;                          // Initialize right partition position

   // Add smallest element from left or right partition to merged numbers
   while (leftPos <= j && rightPos <= k) {
      if ((*numbers)[leftPos] < (*numbers)[rightPos]) {
        *comparisonCounter = *comparisonCounter + 1;
        *memAccessCounter = *memAccessCounter + 2;
         mergedNumbers[mergePos] = (*numbers)[leftPos];
         *memAccessCounter = *memAccessCounter + 1;
         ++leftPos;
      }
      else {
         mergedNumbers[mergePos] = (*numbers)[rightPos];
         *memAccessCounter = *memAccessCounter + 1;
         ++rightPos;

      }
      ++mergePos;
   }

   // If left partition is not empty, add remaining elements to merged numbers
   while (leftPos <= j) {
      mergedNumbers[mergePos] = (*numbers)[leftPos];
      *memAccessCounter = *memAccessCounter + 1;
      ++leftPos;
      ++mergePos;
   }

   // If right partition is not empty, add remaining elements to merged numbers
   while (rightPos <= k) {
      mergedNumbers[mergePos] = (*numbers)[rightPos];
      *memAccessCounter = *memAccessCounter + 1;
      ++rightPos;
      ++mergePos;
   }

   // Copy merge number back to numbers
   for (mergePos = 0; mergePos < mergedSize; ++mergePos) {
      (*numbers)[i + mergePos] = mergedNumbers[mergePos];
      *memAccessCounter = *memAccessCounter + 1;
   }
}