[REPOST] How recursive function works in merge sort ?

Question

1.33/5 (2 votes)

See more:

C#

void partition(int arr[],int low,int high){

    int mid;

    if(low<high){
        mid=(low+high)/2;
        partition(arr,low,mid);
        partition(arr,mid+1,high); // How does the recursion work here?
        mergeSort(arr,low,mid,high);
    }
}

Thanks, mahbub

Posted 2-Jan-14 7:26am

mahbubur rahman

Updated 3-Jan-14 8:07am

Sergey Alexandrovich Kryukov

v3

Add a Solution

2 solutions

Add a Solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CPallini · Accepted Answer · 2014-01-02T07:37:00

Solution 1

Well it works like recursive functions do. In this particular case partition call itself on successive half-ranges of the array (until the range degenerates to a single item, this is the stop condition of its recursion). I suggest you to simulate the function calls with paper and pencil using a short array as input.

Posted 2-Jan-14 7:37am

CPallini

Comments

Sergey Alexandrovich Kryukov 2-Jan-14 14:42pm

Yes, you answered it, a 5. However, I would rather recommend OP to write code instead of asking questions on the code taken from who-knows-where...
—SA

CPallini 2-Jan-14 15:02pm

Thank you.

enhzflep 5-Jan-14 1:21am

I saw this question and couldn't help but think you might get a laugh out of a thread I read earlier this afternoon. Some of the solutions are rather evil and the truly delicious ones ever-so subtly so.. :grin: (the question is tagged code-trolling, and should be considered a joke - at a lazy question-asker's expense)

i need a program where the user inputs an array of doubles and the program outputs the array sorted

Evil B/\stards!

Sergey Alexandrovich Kryukov 5-Jan-14 1:52am

Yes, this would be the most funny computer joke... I actually though at something like that for next April 1st, but my idea is rather the article, with real code, unfortunately, based on already known idea, but not the "implementation".
—SA

enhzflep 5-Jan-14 4:33am

:)There could hardly be a less appropriate time to don the "Works on my machine" badge..

Perhaps I'll have a fun article to read in a couple of months. I'd expect something at least as devious as the sort that discards numbers that are smaller than preceding ones - without documentation, of course.. :thumbs-up: :wink:

m-salahshour · Accepted Answer · 2014-01-04T12:12:00

Dear Friend:

recursive merge_sort works as the following steps:
1- array A[] (with length n) ------> 2 array : array a1[] (with lengs n/2)
array a2[] (with length n/2)

array A[] (with length n): low----mid----high

a1[] (with length n/2) : low----mid
a2[] (with length n/2) : mid+1---- high

2-then sort each of arrays(a1[] & a2[])
a1[] : low----mid
a2[] : mid+1---- high

3-then merger(join) 2 sorted array(a1[] & a2[]) until we obtain 1 sorted array (A[])
and in each of steps :

1- mid=(low+high)/2; finding the center of array

2- partition(arr,low,mid); sorting the lower half of array A[] low----mid

3- partition(arr,mid+1,high); sorting the upper half of array A[] mid+1----high

4- mergeSort(arr,low,mid,high); merging two sorted parts

Good luk

[REPOST] How recursive function works in merge sort ?

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0

[REPOST] How recursive function works in merge sort ?

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0

Existing Members

...or Join us