Bottom-Up Merge Sort Segmentation Fault

[DreamTime]

For a small practice lab, I need to write a Bottom-up Merge Sort that only uses one temporary array, and does not use any recursion. I will run this program on Linux to test it.

I managed to get it to work.... sometimes. It only works with certain sizes of array. For example, if I give it an array with 30 integers, it sorts it with no issues. But if I try to sort an array of 10 integers, I get a segmentation fault. With larger numbers, such as 1000, Linux prints out a huge page of errors.

Here is my code. I don't know what I'm doing that is wrong.

template <class Comparable>
void merge(vector<Comparable> &a, int iLeft, int iMiddle, int iRight, vector<Comparable> &tmp)
{
	int i, j, k;

      i = iLeft;     
      j = iMiddle;
      k = iLeft;

      while ( i < iMiddle || j < iRight )       
      {
         if ( i < iMiddle && j < iRight )
         {  
            if ( a[i] < a[j] )
               tmp[k++] = a[i++];
            else
               tmp[k++] = a[j++];
         }
         else if ( i == iMiddle )
            tmp[k++] = a[j++];      
         else if ( j == iRight )
            tmp[k++] = a[i++];      
      }

      for ( i = iLeft; i < iRight; i++ )
         a[i] = tmp[i];
}


  template <class Comparable>
void mergesort(vector<Comparable> &a) 
{
	int size = a.size();
	vector<Comparable> b(size);   

	for(int subsize = 1; subsize < a.size(); subsize *= 2)
	{
		for(int i = 0; i < a.size(); i += (2 * subsize))
		{
			int left, middle, right;

            left = i;
            middle = i + subsize;
            right  = i + 2*subsize;

            merge( a, left, middle, right, b );
		}
	}
}

[fg109]

You do not check that middle and right are within the bounds of your vector.

#include <iostream>
#include <iomanip>
#include <random>
#include <ctime>

template <class T>
void merge(T * a, T * b, unsigned size, unsigned left, unsigned mid)
{
	unsigned right = mid + mid - left;
	if (right > size)
		right = size;
	unsigned i = left;
	unsigned j = mid;
	unsigned k = left;
	while (i < mid && j < right)
	{
		if (a[i] < a[j])
			b[k++] = a[i++];
		else
			b[k++] = a[j++];
	}
	while (i < mid)
		b[k++] = a[i++];
	while (j < right)
		b[k++] = a[j++];
	for (i = left; i < right; ++i)
		a[i] = b[i];
}

template <class T>
void mergeSort(T * a, unsigned size)
{
	T * b = new T[size];
	for (unsigned subsize = 1; subsize < size; subsize *= 2)
		for (unsigned left = 0, mid = subsize; mid < size; left = mid + subsize, mid = left + subsize)
			merge(a, b, size, left, mid);
	delete[] b;
}

int main()
{
	int array[100];
	std::mt19937 gen;
	std::uniform_int_distribution<> dis(-99, 99);
	gen.seed(time(NULL));

	std::cout << "Before sort:\n\n";
	for (int i = 0; i < 100; ++i)
	{
		array[i] = dis(gen);
		std::cout << std::setw(4) << array[i];
		if (i % 20 == 19)
			std::cout << '\n';
	}
	mergeSort(array, 100);
	std::cout << "\n\nAfter sort:\n\n";
	for (int i = 0; i < 100; ++i)
	{
		std::cout << std::setw(4) << array[i];
		if (i % 20 == 19)
			std::cout << '\n';
	}
	return 0;
}

Before sort:

 -23  34  50 -46  81 -16  20 -29 -11 -24  80  78   9 -55 -33 -76 -22 -78  60  93
  37  79 -36 -75 -45  30 -79 -96  -4 -53  84 -20  51 -95  46  74 -98 -68  29 -63
 -14 -30 -11 -84   6 -34   7  78  40 -35  98 -76 -56 -12  67  76 -43 -61 -61   9
  73 -66 -32 -23  89  51   8  60  14  19 -86 -10 -41 -66 -71 -45  32 -29  85 -51
  27  44  47  58  48 -70  25 -64  -9 -40  75  -5 -95 -43 -51  99  66  92  76   5


After sort:

 -98 -96 -95 -95 -86 -84 -79 -78 -76 -76 -75 -71 -70 -68 -66 -66 -64 -63 -61 -61
 -56 -55 -53 -51 -51 -46 -45 -45 -43 -43 -41 -40 -36 -35 -34 -33 -32 -30 -29 -29
 -24 -23 -23 -22 -20 -16 -14 -12 -11 -11 -10  -9  -5  -4   5   6   7   8   9   9
  14  19  20  25  27  29  30  32  34  37  40  44  46  47  48  50  51  51  58  60
  60  66  67  73  74  75  76  76  78  78  79  80  81  84  85  89  92  93  98  99