[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

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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