I'm studying a algorithm called merge sort, in which i did in Java. But, I'm having problems to understand it.

So, when I run the program, is called the method

**mergeSort**for to make the sorting of numbers. After , make the 'if', then is executed the method

**mergeSort(A, p, q);**three times, and just after is executed the method

**mergeSort(A, q+1, r)**. Why that happens ?

Thanks you!

Gustavo Siqueira wrote:Hi, everyone!

I'm studying a algorithm called merge sort, in which i did in Java. But, I'm having problems to understand it.

What do you mean by "in which I did in Java?" Surely you do not mean that you wrote the code, because then you would understand it, right? So if you didn't write it, then where do you get it, can you QuoteYourSources?

Gustavo Siqueira wrote:So, when I run the program, is called the method

mergeSortfor to make the sorting of numbers. After , make the 'if', then is executed the methodmergeSort(A, p, q);three times, and just after is executed the methodmergeSort(A, q+1, r). Why that happens ?

This is recursion. In this scenario you take a task and you split it into smaller parts, and you do that over and over again until you get to parts that are so easy you can handle them. Then you put everything back together as the method stack unrolls.

Try a search for recursion and you will get lots of useful info.

Below is the code you posted.

Gustavo Siqueira wrote:

So, when I run the program, is called the methodmergeSortfor to make the sorting of numbers. After , make the 'if', then is executed the methodmergeSort(A, p, q);three times, and just after is executed the methodmergeSort(A, q+1, r). Why that happens ?

Thanks you!

Steve

Gustavo Siqueira wrote:I'm reading the book "Introduction to Algorithms". So, I caught this algorithm in this book. You no response my question: Why the method is executed three times for after to go to other method following ?

I most certainly did. It is called recursion. I like to think of these things as 'halves' of execusion. With the

`mergeSort(A,p,q)`being the left half, and

`mergeSort(A,q+1,r)`being the right half. That makes it easier to follow along on paper. Draw a line down for the original method call.

When you see the 'left call' draw a line angled to the left.

Remember that the code in the left call gets executed before the rest of the calling method, so follow the left call's execution. You will see it comes to another left call.

I am guessing from the output you said happens that if you continue to trace it out on paper you would reach a third left call:

This probably reaches a 'base case:' a case where no more recursion is needed, so the execution on this level completes, and control returns up the method calling tree, which you right by an upward diagonal parallel to the last left call:

When control returns to the parent, it would meet the right call, so you draw a diagonal line to the right:

So if this is how the execution traced out you would see that there would be three left calls, followed by a right call. The actual 'depth' of the left calls depends on the data, and right calls can lead to further left calls, so you might get something with more complex branching if the data set is large. Maybe light this (sorry I never was very good at ascii art):

Steve

I'm comprising. So, once that this algorithm is called divide-and-conquer, is a ways for to solve a given problem. Alright. But, because it is considered like worst-case in (theta of n-squared) ?

In terms of running time, this delay algorithm for run. In addition of algorithm to solve a problem, it has that run in time fast. There is a algorithm called Insertion sort, that in little lines make sorted of numbers.

For example, see the following exercise from book "Introduction to Algorithms":

We can express insertion sort as a recursive procedure as follows. In order to sort A[1..n], we recursively sort A[1..n-1] and then insert A[n] into the sorted array A[1..n-1]. Write a recurrence for the worst-case running time of this recursive version of insertion sort.

If possible, do you can me say exactly what means that such of 'worst-case' ? I really can not understand it.

lets say we have a sorted array with the values of 1,2,3,4,5.

now let's say we have a linear or sequential search (we start at position 1, go to 2, go to 3.....)

ok, now if we want to find the best-case, average-case or worst-case for this....

if we want to look for 1, we test position 1 (found)

if we want to look for 1, we test position 1 (not found), then test position 2 (found)

so you should see the pattern.

In this case.....

Best-case is order of (1) or O(c). this is looking for 1

Worst-case would be 5 or order (n) - that is we had to run the entire array, if the array was 10000000 positions and that position had 5 we would have to go through all of others.

Now average case would be 3 for this (or in general O(n/2).

HTH

-steve

Consider Paul's rocket mass heater. |