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.
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);
}
}
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;
}
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;
}
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;
}
#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;
}
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.
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);
}
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;
}
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);
}
}
Source: Stackoverflow.com