Want to improve this question? Add details and clarify the problem by editing this post.
Closed 6 years ago.
here is the code to partition in merge sort..am not able to understand actually how does recusrion works in it!!
MERGE SORT PARTITION
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);
mergeSort(arr, low, mid, high);
}
}
actually am getting messed up in many recursive problems and am not able to understand how does system stack works in recursion...
am a beginner..
Lets take an example of
Array arr ={ 5,2,4,7,1,3,2,6}; 8 elements
1 2 3 4 5 6 7
^(partition+mergeSort)
|
+------------+ +---------------+
| |
2 4 5 7 1 2 3 6
^ (partition+mergeSort) ^ (partition+mergeSort)
| |
+--+ +---+ +--+ +---+
| | | |
2 5 4 7 1 3 2 6
^ (partition+mergeSort) ^ (partition+mergeSort)
| |
+---+ +---+ +---+ +---+
| | | |
5 2 4 7 1 3 2 6
4 elements 4 elements
Initial Unsorted Array
Go from bottom to top, two arrays are formed with
arr[low...mid] and
arr[mid+1...high] on each recursive calls, and finally they both get merged.
Partitioning & Merging process continues as long as low < high
Its just an example how mergeSort is working here, you can follow the code with this example.
A call with partition(arr, 0,7) on this unsorted array will have :
On first pass mid =3
arr gets divided into 2 parts using
partion(arr,0,3) and partion(arr,4,7)
Each of those partitions are again spitted up into two parts i.e for 0 to 3 gets divided into (0,1) & (2,3) , further again (0,1) and (1,1) . (1,1) is skipped as low > high this last 2 elements are merged up with mergeSort
A group of such small sorted array are then finally merged up as it comes out of recursion on subsequent passes.
This is bit difficult to explain here, in textual format, try it on paper,I'm sure you can figure it out, with even more smaller array, say for 4 elements.
I'll try to make recursive functions simpler for you. Take for example a small example of factorial pseudo-code:
int fact(n)
{
if(n==1 || n==0) return 1;
else
return (n*fact(n-1));
}
What this will do is create a stack of functions. Suppose I call fact(3) this will make a stack like:
fact(0)
fact(1)
fact(2)
fact(3)
where each function is pushed into the stack. First fact(3) is called. fact(3) calls fact(2). So after the passes --
Stack build up:
fact(0)
fact(1) fact(1)
fact(2) fact(2) fact(2)
empty --> fact(3) ---> fact(3) --> fact(3) --> fact(3)
Now the function catches n=0 and returns 1. Now the functions start popping out.
Stack :
fact(0) -----> (returns 1) = 1
fact(1) -----> (returns 1) * 1 (1's popped out)
fact(2) -----> (returns 2) * 1 (1 is actually 1*1)
fact(3) -----> (returns 3) * (2 = 2*1*1)
----->6
EDIT:Added pop functionally. As for the sorting stack kindly check out @P0W's answer.
Trying taking a small example and build your stack. Then move onto complex ones. Remember practice is the key. This is how recursive functions work as a stack.
Hope it helps. :)
