implementing merge sort in C++

Question

I have studied the theory of the merge sort but don't have any idea of how to implement it in C++. My question is, merge sort creates arrays in recursion. But when implementing, how do we create arrays in runtime? or what is the general approach for this?

Thanks.

Answer 1

This is my version (simple and easy):
uses memory only twice the size of original array.
[ a is the left array ] [ b is the right array ] [ c used to merge a and b ] [ p is counter for c ]

void MergeSort(int list[], int size)
{
    int blockSize = 1, p;
    int *a, *b;
    int *c = new int[size];
    do
    {
        for (int k = 0; k < size; k += (blockSize * 2))
        {
            a = &list[k];
            b = &list[k + blockSize];
            p = 0;
            for (int i = 0, j = 0; i < blockSize || j < blockSize;)
            {
                if ((j < blockSize) && ((k + j + blockSize) >= size))
                {
                    ++j;
                }
                else if ((i < blockSize) && ((k + i) >= size))
                {
                    ++i;
                }
                else if (i >= blockSize)
                {
                    c[p++] = b[j++];
                }
                else if (j >= blockSize)
                {
                    c[p++] = a[i++];
                }
                else if (a[i] >= b[j])
                {
                    c[p++] = b[j++];
                }
                else if (a[i] < b[j])
                {
                    c[p++] = a[i++];
                }
            }
            for (int i = 0; i < p; i++)
            {
                a[i] = c[i];
            }
        }
        blockSize *= 2;
    } while (blockSize < size);
}

Answer 2

The problem with merge sort is the merge, if you don't actually need to implement the merge, then it is pretty simple (for a vector of ints):

#include <algorithm>
#include <vector>
using namespace std;

typedef vector<int>::iterator iter;

void mergesort(iter b, iter e) {
    if (e -b > 1) {
        iter m = b + (e -b) / 2;
        mergesort(b, m);
        mergesort(m, e);
        inplace_merge(b, m, e);
    }
}

Answer 3

Based on the code here: http://cplusplus.happycodings.com/algorithms/code17.html

// Merge Sort

#include <iostream>
using namespace std;

int a[50];
void merge(int,int,int);
void merge_sort(int low,int high)
{
 int mid;
 if(low<high)
 {
  mid = low + (high-low)/2; //This avoids overflow when low, high are too large
  merge_sort(low,mid);
  merge_sort(mid+1,high);
  merge(low,mid,high);
 }
}
void merge(int low,int mid,int high)
{
 int h,i,j,b[50],k;
 h=low;
 i=low;
 j=mid+1;

 while((h<=mid)&&(j<=high))
 {
  if(a[h]<=a[j])
  {
   b[i]=a[h];
   h++;
  }
  else
  {
   b[i]=a[j];
   j++;
  }
  i++;
 }
 if(h>mid)
 {
  for(k=j;k<=high;k++)
  {
   b[i]=a[k];
   i++;
  }
 }
 else
 {
  for(k=h;k<=mid;k++)
  {
   b[i]=a[k];
   i++;
  }
 }
 for(k=low;k<=high;k++) a[k]=b[k];
}
int main()
{
 int num,i;

cout<<"*******************************************************************
*************"<<endl;
 cout<<"                             MERGE SORT PROGRAM
"<<endl;

cout<<"*******************************************************************
*************"<<endl;
 cout<<endl<<endl;
 cout<<"Please Enter THE NUMBER OF ELEMENTS you want to sort [THEN 
PRESS
ENTER]:"<<endl;
 cin>>num;
 cout<<endl;
 cout<<"Now, Please Enter the ( "<< num <<" ) numbers (ELEMENTS) [THEN
PRESS ENTER]:"<<endl;
 for(i=1;i<=num;i++)
 {
  cin>>a[i] ;
 }
 merge_sort(1,num);
 cout<<endl;
 cout<<"So, the sorted list (using MERGE SORT) will be :"<<endl;
 cout<<endl<<endl;

 for(i=1;i<=num;i++)
 cout<<a[i]<<"  ";

 cout<<endl<<endl<<endl<<endl;
return 1;

}

Answer 4

This would be easy to understand:

#include <iostream>

using namespace std;

void Merge(int *a, int *L, int *R, int p, int q)
{
    int i, j=0, k=0;
    for(i=0; i<p+q; i++)
    {
        if(j==p)                       //When array L is empty
        {
            *(a+i) = *(R+k);
            k++;
        }
        else if(k==q)                  //When array R is empty
        {
            *(a+i) = *(L+j);
            j++;
        }
        else if(*(L+j) < *(R+k))  //When element in L is smaller than element in R
        {
            *(a+i) = *(L+j);
            j++;
        }
        else   //When element in R is smaller or equal to element in L
        {
            *(a+i) = *(R+k);
            k++;
        }
    }
}

void MergeSort(int *a, int len)
{
    int i, j;
    if(len > 1)
    {
        int p = len/2 + len%2;      //length of first array
        int q = len/2;              //length of second array
        int L[p];                   //first array
        int R[q];                   //second array
        for(i=0; i<p; i++)
        {
            L[i] = *(a+i);      //inserting elements in first array
        }
        for(i=0; i<q; i++)
        {
            R[i] = *(a+p+i);    //inserting elements in second array
        }
        MergeSort(&L[0], p);
        MergeSort(&R[0], q);
        Merge(a, &L[0], &R[0], p, q);   //Merge arrays L and R into A
    }
    else
    {
        return;        //if array only have one element just return
    }
}

int main()
{
    int i, n;
    int a[100000];
    cout<<"Enter numbers to sort. When you are done, enter -1\n";
    i=0;
    while(true)
    {
        cin>>n;
        if(n==-1)
        {
            break;
        }
        else
        {
            a[i] = n;
            i++;
        }
    }
    int len = i;
    MergeSort(&a[0], len);
    for(i=0; i<len; i++)
    {
        cout<<a[i]<<" ";
    }

    return 0;
}

Answer 5

I have completed @DietmarKühl s way of merge sort. Hope it helps all.

template <typename T>
void merge(vector<T>& array, vector<T>& array1, vector<T>& array2) {
    array.clear();

    int i, j, k;
    for( i = 0, j = 0, k = 0; i < array1.size() && j < array2.size(); k++){
        if(array1.at(i) <= array2.at(j)){
            array.push_back(array1.at(i));
            i++;
        }else if(array1.at(i) > array2.at(j)){
            array.push_back(array2.at(j));
            j++;
        }
        k++;
    }

    while(i < array1.size()){
        array.push_back(array1.at(i));
        i++;
    }

    while(j < array2.size()){
        array.push_back(array2.at(j));
        j++;
    }
}

template <typename T>
void merge_sort(std::vector<T>& array) {
    if (1 < array.size()) {
        std::vector<T> array1(array.begin(), array.begin() + array.size() / 2);
        merge_sort(array1);
        std::vector<T> array2(array.begin() + array.size() / 2, array.end());
        merge_sort(array2);
        merge(array, array1, array2);
    }
}

Answer 6

Here's a way to implement it, using just arrays.

#include <iostream>
using namespace std;

//The merge function
void merge(int a[], int startIndex, int endIndex)
{

int size = (endIndex - startIndex) + 1;
int *b = new int [size]();

int i = startIndex;
int mid = (startIndex + endIndex)/2;
int k = 0;
int j = mid + 1;

while (k < size)
{   
    if((i<=mid) && (a[i] < a[j]))
    {
        b[k++] = a[i++];
    }
    else
    {
        b[k++] = a[j++];
    }

}

for(k=0; k < size; k++)
{
    a[startIndex+k] = b[k];
}

delete []b;

}

//The recursive merge sort function
void merge_sort(int iArray[], int startIndex, int endIndex)
{
int midIndex;

//Check for base case
if (startIndex >= endIndex)
{
    return;
}   

//First, divide in half
midIndex = (startIndex + endIndex)/2;

//First recursive call 
merge_sort(iArray, startIndex, midIndex);

//Second recursive call 
merge_sort(iArray, midIndex+1, endIndex);

merge(iArray, startIndex, endIndex);

}



//The main function
int main(int argc, char *argv[])
{
int iArray[10] = {2,5,6,4,7,2,8,3,9,10};

merge_sort(iArray, 0, 9);

//Print the sorted array
for(int i=0; i < 10; i++)
{
    cout << iArray[i] << endl;
}

return 0;    
}

Answer 7

#include <iostream>
using namespace std;

template <class T>
void merge_sort(T array[],int beg, int end){
    if (beg==end){
        return;
    }
    int mid = (beg+end)/2;
    merge_sort(array,beg,mid);
    merge_sort(array,mid+1,end);
    int i=beg,j=mid+1;
    int l=end-beg+1;
    T *temp = new T [l];
    for (int k=0;k<l;k++){
        if (j>end || (i<=mid && array[i]<array[j])){
            temp[k]=array[i];
            i++;
        }
        else{
            temp[k]=array[j];
            j++;
        }
    }
    for (int k=0,i=beg;k<l;k++,i++){
        array[i]=temp[k];
    }
    delete temp;
}

int main() {
    float array[] = {1000.5,1.2,3.4,2,9,4,3,2.3,0,-5};
    int l = sizeof(array)/sizeof(array[0]);
    merge_sort(array,0,l-1);
    cout << "Result:\n";
    for (int k=0;k<l;k++){
        cout << array[k] << endl;
    }
    return 0;
}

Answer 8

I know this question has already been answered, but I decided to add my two cents. Here is code for a merge sort that only uses additional space in the merge operation (and that additional space is temporary space which will be destroyed when the stack is popped). In fact, you will see in this code that there is not usage of heap operations (no declaring new anywhere).

Hope this helps.

    void merge(int *arr, int size1, int size2) {
        int temp[size1+size2];
        int ptr1=0, ptr2=0;
        int *arr1 = arr, *arr2 = arr+size1;

        while (ptr1+ptr2 < size1+size2) {
            if (ptr1 < size1 && arr1[ptr1] <= arr2[ptr2] || ptr1 < size1 && ptr2 >= size2)
                temp[ptr1+ptr2] = arr1[ptr1++];

            if (ptr2 < size2 && arr2[ptr2] < arr1[ptr1] || ptr2 < size2 && ptr1 >= size1)
                temp[ptr1+ptr2] = arr2[ptr2++];
        }   

        for (int i=0; i < size1+size2; i++)
            arr[i] = temp[i];
    }   

    void mergeSort(int *arr, int size) {
        if (size == 1)
            return;

        int size1 = size/2, size2 = size-size1;
        mergeSort(arr, size1);
        mergeSort(arr+size1, size2);
        merge(arr, size1, size2);
    } 

    int main(int argc, char** argv) {
         int num;
         cout << "How many numbers do you want to sort: ";
         cin >> num;
         int a[num];
         for (int i = 0; i < num; i++) {
           cout << (i + 1) << ": ";
           cin >> a[i];
         }   

         // Start merge sort
         mergeSort(a, num);

         // Print the sorted array
         cout << endl;
         for (int i = 0; i < num; i++) {
           cout << a[i] << " ";
         }   
         cout << endl;

         return 0;
    } 

Answer 9

I've rearranged the selected answer, used pointers for arrays and user input for number count is not pre-defined.

#include <iostream>

using namespace std;

void merge(int*, int*, int, int, int);

void mergesort(int *a, int*b, int start, int end) {
  int halfpoint;
  if (start < end) {
    halfpoint = (start + end) / 2;
    mergesort(a, b, start, halfpoint);
    mergesort(a, b, halfpoint + 1, end);
    merge(a, b, start, halfpoint, end);
  }
}

void merge(int *a, int *b, int start, int halfpoint, int end) {
  int h, i, j, k;
  h = start;
  i = start;
  j = halfpoint + 1;

  while ((h <= halfpoint) && (j <= end)) {
    if (a[h] <= a[j]) {
      b[i] = a[h];
      h++;
    } else {
      b[i] = a[j];
      j++;
    }
    i++;
  }
  if (h > halfpoint) {
    for (k = j; k <= end; k++) {
      b[i] = a[k];
      i++;
    }
  } else {
    for (k = h; k <= halfpoint; k++) {
      b[i] = a[k];
      i++;
    }
  }

  // Write the final sorted array to our original one
  for (k = start; k <= end; k++) {
    a[k] = b[k];
  }
}

int main(int argc, char** argv) {
  int num;
  cout << "How many numbers do you want to sort: ";
  cin >> num;
  int a[num];
  int b[num];
  for (int i = 0; i < num; i++) {
    cout << (i + 1) << ": ";
    cin >> a[i];
  }

  // Start merge sort
  mergesort(a, b, 0, num - 1);

  // Print the sorted array
  cout << endl;
  for (int i = 0; i < num; i++) {
    cout << a[i] << " ";
  }
  cout << endl;

  return 0;
}

Answer 10

To answer the question: Creating dynamically sized arrays at run-time is done using std::vector<T>. Ideally, you'd get your input using one of these. If not, it is easy to convert them. For example, you could create two arrays like this:

template <typename T>
void merge_sort(std::vector<T>& array) {
    if (1 < array.size()) {
        std::vector<T> array1(array.begin(), array.begin() + array.size() / 2);
        merge_sort(array1);
        std::vector<T> array2(array.begin() + array.size() / 2, array.end());
        merge_sort(array2);
        merge(array, array1, array2);
    }
}

However, allocating dynamic arrays is relatively slow and generally should be avoided when possible. For merge sort you can just sort subsequences of the original array and in-place merge them. It seems, std::inplace_merge() asks for bidirectional iterators.