1
\$\begingroup\$

I have recently learned Merge Sort algorithm in C++ with 2 ways of writing it.

1st Way:

    void merge(int arr[],int low,int mid,int high){
        const int n1=(mid-low+1);
        const int n2=(high-mid);
        int*a=new int[n1],*b=new int[n2];//dynamically allocated because of MSVC compiler
        for(int i=0;i<n1;i++)
            a[i]=arr[low+i];
        for(int i=0;i<n2;i++)
            b[i]=arr[mid+1+i];
        int i=0,j=0,k=low;
        while(i<n1 && j<n2){
                if(a[i]<b[j]){
                arr[k]=a[i];
                i++;
            }else{
                arr[k]=b[j];
                j++;
            }
            k++;
        }
        while(i<n1){
            arr[k]=a[i];
            k++,i++;
        }
    
        while(j<n2){
            arr[k]=b[j];
            k++,j++;
        }
        delete[]a;
        delete[]b;
    }

    void mergeSort(int arr[],int start,int end){
     if(start<end){
        int mid=(start+end)/2;
        mergeSort(arr,start,mid);
        mergeSort(arr,mid+1,end);
        merge(arr,start,mid,end);
    }
}

int main(){
    int arr[]={9,14,4,8,6,7,5,2,1};
    unsigned size=sizeof(arr)/sizeof(arr[0]);
    printArray(arr,size);
    mergeSort(arr,0,size-1);
    printArray(arr,size);
    return 0;
    }

2nd Way:

    void merge(int arr[],int temp[],int low,int mid,int high){
        //passed temp array from the beginning 
        int i=low,k=low,j=mid+1;
        while(i<=mid && j<=high){
            if(arr[i]<arr[j]){
                temp[k]=arr[i];
                i++;
            }else{
                temp[k]=arr[j];
                j++;
            }
            k++;
        }
        while(i<=mid){
            temp[k]=arr[i];
            k++,i++;
        }
        while(j<=high){
            temp[k]=arr[j];
            k++,j++;
        }
        for(int i=low;i<=high;i++)
            arr[i]=temp[i];
    }

   void mergeSort(int arr[],int temp[],int start,int end){
       if(start<end){
        int mid=(start+end)/2;
        mergeSort(arr,temp,start,mid);
        mergeSort(arr,temp,mid+1,end);
        merge(arr,temp,start,mid,end);
    }
}

int main(){
    int arr[]={9,14,4,8,6,7,5,2,1};
    unsigned size=sizeof(arr)/sizeof(arr[0]);
    int*buffer=new int[size];
    printArray(arr,size);
    mergeSort(arr,buffer,0,size-1);
    printArray(arr,size);
    delete[]buffer;
    return 0;
}

Edited:

printArray method:

void printArray(int arr[],int n){
    for(int i=0;i<n;i++)
        printf("%d ",arr[i]);
    printf("\n");
}

I tried out both the methods on LeetCode exercise- Sort an Array, here the 1st method gave less runtime than the 2nd. Which way of writing the merge function is better and more efficient?

\$\endgroup\$
1
  • \$\begingroup\$ printArray() seems to be undefined. \$\endgroup\$ Sep 26 at 16:10
0
\$\begingroup\$

I haven't got time to do this comprehensively but here is a start...

Which method is better must be decided by what is important to you.

Both methods are recursive. The pro's and con's of that are worth reading up about. At its heart recursion hammers the call stack (which is usually very limited in size relative to heap memory) and can cause programs to crash after a fairly modest number of recursive calls.

The first method dynamically allocates memory inside merge(). This impacts the cost in memory terms but (taking your word for it - see the remark on how to measure below) gives it the speed advantage.

The second method works "in place", making its use of memory more efficient at the expense of speed.

The analysis of algorithms is a big topic on its own. Read up on the basics of Big O notation Big O Notation. You will probably find that assessing your algorithms for both speed and memory in relation to the number of elements being sorted will answer your own question.

What should be important to you in choosing? If the arrays you need to sort can become large then space efficiency (stability under load) should probably be the dominant consideration (but then I'd also spend time on getting rid of the recursion).

How should you measure? Start here: Benchmarking

\$\endgroup\$
0
\$\begingroup\$

void merge(int arr[],int low,int mid,int high)
That's not normal C++, for two reasons. First, int arr[] is actually a pointer and is discouraged from writing it this way. Second, you should be using iterators rather than an "array" and index values.


const int n1=(mid-low+1);
const int n2=(high-mid);
int*a=new int[n1],*b=new int[n2];//dynamically allocated because of MSVC compiler

What do you mean "because of MSVC compiler"? If you expected to write a C-style VLA, that's not allowed in C++. n1 and n2 are not compile-time constants but merely run-time local variables that happen to be constant once initialized.

⧺C.149 — no naked new or delete.

Use std::vector for this.


for(int i=0;i<n1;i++)
            a[i]=arr[low+i];
for(int i=0;i<n2;i++)
            b[i]=arr[mid+1+i];

I think you want std::copy_n here. Don't write loops — use algorithms. Same with other half of the function which copies the two parts into temp or arr.

 unsigned size=sizeof(arr)/sizeof(arr[0]);

Don't do that. use std::size(arr) to get that value. But ideally you don't need that value; you'll be using begin and end instead.


See also the answers to similar code
Parallezing merge step and divide step in mergesort algorithm with OpenMP

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.