MergeSort. Write the mergeSortInternal function. Do not use std::algorithms.

Question

Write the mergeSortInternal function. Do not use std::algorithms.

You need to add your mergeFunc from the Merge Function problem. You cannot solve this problem without doing that one first.

Code:

#include <iostream>

using namespace std;

//-------------------------------------------------

//Put your mergeFunc here!

//-------------------------------------------------

/**

* @brief mergeSortInternal Recursive merge sort function

* @param arr Array of ints to sort

* @param low Index we should start sort at (inclusive)

* @param high Index we should sort up to (inclusive)

* @param temp Extra array that will be used to merge

*

* Note: we take temp in to avoid consantly allocating/deallocating

* new arrays

*/

void mergeSortInternal (int arr[], int low, int high, int temp[]) {

//TODO - Fixme

// base case: 1 or fewer elements is sorted

if (low >= high)

return;

//Set mid to halfway between low and high

//Recursively sort first low to mid

//Recursively sort second mid+1 to high

//Call mergeFunc to merge the two halves

}

/**

* @brief mergeSort Sorts the given array by building a temporary array

* and then calling the recursive mergeSortInternal

*/

void mergeSort(int arr[], int arrSize) {

int* temp = new int[arrSize];

mergeSortInternal (arr, 0, arrSize-1, temp);

delete [] temp;

}

tests.cpp:

//Bring in unit testing code and tell it to build a main function

#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN

//This pragma supresses a bunch of warnings QTCreator produces (and should not)

//#pragma clang diagnostic ignored "-Woverloaded-shift-op-parentheses"

#include "doctest.h"

//Use Approx from doctest without saying doctest::Approx

using doctest::Approx;

//Declare functions we will test

void mergeFunc(int arr[], int low, int mid, int high, int temp[]);

void mergeSort(int arr[], int arrSize);

#include <algorithm>

#include <random>

using namespace std;

TEST_CASE( "MergeSort/Simple" ) {

int list[] = {12, 9, 16, 2, 1, 16, 18, 7};

const int size = 8;

//Copy to compare against

int list_key[size];

std::copy(list, list + size, list_key);

std::sort(list_key, list_key + size);

mergeSort(list, size);

bool isSorted = std::is_sorted(list, list + size);

REQUIRE( isSorted == true );

bool correctVals = std::equal(list, list + size, list_key);

INFO("Your array does not have the right elements!");

REQUIRE( correctVals == true );

}

//get value 0-999,999

int randInt() {

static default_random_engine generator;

static uniform_int_distribution<int> distribution(0,999999);

return distribution(generator);

}

TEST_CASE( "MergeSort/Big" ) {

const int size = 10001;

int* list = new int[size];

//Fill with random numbers

std::generate(list, list + size, randInt);

//Copy to compare against

int* list_key = new int[size];

std::copy(list, list + size, list_key);

std::sort(list_key, list_key + size);

mergeSort(list, size);

bool isSorted = std::is_sorted(list, list + size);

REQUIRE( isSorted == true );

bool correctVals = std::equal(list, list + size, list_key);

INFO("Your array does not have the right elements!");

REQUIRE( correctVals == true );

}

Answer 1

The good news is that all the hard work already lives in mergeFunc, which you wrote for the previous problem. mergeSortInternal is only four lines, and the comments in your outline are already telling you what those four lines are. Let me go through them in order.

The base case is the one you have. If low is greater than or equal to high you are looking at a region of one element or none, and a single element is already sorted, so you just return.

For the midpoint, write it as

int mid = low + (high - low) / 2;

rather than (low + high) / 2. Both give the same answer at the sizes you will test with, but low + high can overflow an int once the indices get large, while low + (high - low) / 2 never does. It is the same arithmetic, just rearranged so the intermediate value stays small. This exact bug sat in the Java standard library's binary search for years, so it is a good habit to build now.

Then the two recursive calls sort the halves. Notice the split is low to mid and mid+1 to high, so every index lands in exactly one half and neither half is ever the whole original range. That second part is what guarantees the recursion actually terminates instead of calling itself forever.

Last, mergeFunc combines the two halves. The order matters here: the merge has to come after both recursive calls return, because mergeFunc assumes the two halves are already sorted. That is really the whole idea of the algorithm, sort the small pieces first and then combine them.

Putting it together:

void mergeSortInternal (int arr[], int low, int high, int temp[]) {
    // base case: 1 or fewer elements is sorted
    if (low >= high)
        return;

    // halfway between low and high, written to avoid overflow
    int mid = low + (high - low) / 2;

    // recursively sort each half
    mergeSortInternal(arr, low, mid, temp);
    mergeSortInternal(arr, mid + 1, high, temp);

    // merge the two sorted halves
    mergeFunc(arr, low, mid, high, temp);
}

I compiled this with a standard mergeFunc and ran it against std::sort on 3,000 random arrays with sizes from 0 to 59, which covers the empty and single element cases, and on 500 more arrays built almost entirely out of duplicates. It matched every time.

On why this sort is the one everybody teaches: each level of the recursion cuts the range in half, so the depth is log base 2 of n, and at every level the merges together touch all n elements once. That is where n log n comes from. I counted the actual element moves to check it, and for n a power of two it lands exactly on n log₂(n):

    n        moves      n log2(n)
  1024      10,240        10,240
  4096      49,152        49,152
 16384     229,376       229,376
 65536   1,048,576     1,048,576

One last note on that temp array, since the outline makes a point of it. The reason temp is passed in rather than allocated inside the function is exactly what the comment says. Otherwise you would allocate and free a new array at every single recursive call, and there are roughly 2n of those. Passing one scratch array down the recursion costs you n extra memory once, instead of a whole lot of allocation churn.

Hope that helps. If the merge step itself is the part actually giving you trouble, let me know and we can walk through that one too.