Menu
Most of the mergesort implementations I see are similar to this. intro to algorithms book along with online implentations I search for. My recursion chops don't go much further than messing with Fibonacci generation (which was simple enough) so maybe it's the multiple recursions blowing my mind, but I can't even step through the code and understand whats going on even before I even hit the merge function.
How is it stepping through this? Is there some strategy or reading I should undergo to better understand the process here?
void mergesort(int *a, int*b, int low, int high) { int pivot; if(low<high) { pivot=(low+high)/2; mergesort(a,b,low,pivot); mergesort(a,b,pivot+1,high); merge(a,b,low,pivot,high); } } and the merge(although frankly I'm mentally stuck before I even get to this part)
void merge(int *a, int *b, int low, int pivot, int high) { int h,i,j,k; h=low; i=low; j=pivot+1; while((h<=pivot)&&(j<=high)) { if(a[h]<=a[j]) { b[i]=a[h]; h++; } else { b[i]=a[j]; j++; } i++; } if(h>pivot) { for(k=j; k<=high; k++) { b[i]=a[k]; i++; } } else { for(k=h; k<=pivot; k++) { b[i]=a[k]; i++; } } for(k=low; k<=high; k++) a[k]=b[k]; } 
260
The merge sort algorithm is a sorting algorithm that sorts a collection by breaking it into half. It then sorts those two halves, and then merges them together, in order to form one, completely sorted collection. And, in most implementations of merge sort, it does all of this using recursion.
Merge sort keeps on dividing the list into equal halves until it can no more be divided. By definition, if it is only one element in the list, it is sorted. Then, merge sort combines the smaller sorted lists keeping the new list sorted too. Step 1 − if it is only one element in the list it is already sorted, return.
We defined a recursive method MergeSort() to divide the input array in the middle and recursively sort each part. So we expect to call MergeSort log n times. Since each recursive step is one half the length of n .
It is possible to come up with a formula for recurrences of the form T(n) = aT(n/b) + nc (T(1) = 1). This is called the master method. – Merge-sort ⇒ T(n)=2T(n/2) + n (a = 2,b = 2, and c = 1).
MERGE SORT:
1) Split the array in half
2) Sort the left half
3) Sort the right half
4) Merge the two halves together
129
I think the "sort" function name in MergeSort is a bit of a misnomer, it should really be called "divide".
Here is a visualization of the algorithm in process.
Each time the function recurses, it's working on a smaller and smaller subdivision of the input array, starting with the left half of it. Each time the function returns from recursion, it will continue on and either start working on the right half, or recurse up again and work on a larger half.
Like this
[************************]mergesort [************]mergesort(lo,mid) [******]mergesort(lo,mid) [***]mergesort(lo,mid) [**]mergesort(lo,mid) [**]mergesort(mid+1,hi) [***]merge [***]mergesort(mid+1,hi) [**]mergesort*(lo,mid) [**]mergesort(mid+1,hi) [***]merge [******]merge [******]mergesort(mid+1,hi) [***]mergesort(lo,mid) [**]mergesort(lo,mid) [**]mergesort(mid+1,hi) [***]merge [***]mergesort(mid+1,hi) [**]mergesort(lo,mid) [**]mergesort(mid+1,hi) [***]merge [******]merge [************]merge [************]mergesort(mid+1,hi) [******]mergesort(lo,mid) [***]mergesort(lo,mid) [**]mergesort(lo,mid) [**]mergesort(mid+1,hi) [***]merge [***]mergesort(mid+1,hi) [**]mergesort(lo,mid) [**]mergesort(mid+1,hi) [***]merge [******]merge [******]mergesort(mid+1,hi) [***]mergesort(lo,mid) [**]mergesort*(lo,mid) [**]mergesort(mid+1,hi) [***]merge [***]mergesort(mid+1,hi) [**]mergesort(lo,mid) [**]mergesort(mid+1,hi) [***]merge [******]merge [************]merge [************************]merge If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
