Question

Write a program that performs a merge-sort algorithm without using a recursion. Only using pointers.
C++ programming language; #include<iostream>

Answer 1

Code for the Given Problem:

#include<iostream>
using namespace std;
/* merge function to merge the sorted smaller arrays */
void
merge (int **a, int ibegin, int imid, int iend, int **b)
{
  int i = ibegin, j = imid;
  for (int k = ibegin; k < iend; k++)
    b[k] = a[i < imid && (j >= iend || *a[i] <= *a[j]) ? i++ : j++];
}

/* function to split the array  */
void
splitmerge (int **b, int ibegin, int iend, int **a)
{
  if (iend - ibegin < 2)
    return;
  int imid = (iend + ibegin) / 2;
  splitmerge (a, ibegin, imid, b);
  splitmerge (a, imid, iend, b);
  merge (b, ibegin, imid, iend, a);
}

/* mergesort function which sorts and returns the sorted array */
int **
mergesort (int *a, int size)
{
  int **ret = new int *[size];
  int **tmp = new int *[size];
  for (int i = 0; i < size; i++)
    ret[i] = tmp[i] = a + i;
  splitmerge (tmp, 0, size, ret);
  delete (tmp);
  return ret;
}

/* driver program */
int
main ()
{
  /* taking the inputs */
  int n;
  cout << "Enter the size of array :";
  cin >> n;
  int a[n];
  cout << "Enter the array : ";
  for (int i = 0; i < n; i++)
    {
      cin >> a[i];
    }
  int size = sizeof a / sizeof a[0];
  /* calling mergesort function */
  int **ret = mergesort (a, size);
  /* printing the sorted array */
  cout << "Sorted Array is : ";
  for (int i = 0; i < size; i++)
    {
      cout << (*ret[i]) << " ";
    }
  cout << endl;

  delete (ret);
  return 0;
}

Screenshot for reference:

Sample Output: