# Few questions about Mergesort and Recirsion algorithms

1. Can we use recursive algorithm to find the greatest element of a finite list when numbers are unsorted.
2. How to use recursive algorithm to find the least element of a finite list of unsorted numbers where repetitions of number is allowed.
3. How can Mergesort calls itself n^2 times on a list with n numbers.
4. Is it true if the input list has only 3 numbers, then Mergesort does not need the merging step.
5. Can we find number of elements in a finite list with a recursive algorithm.

Little explanations will be helpful to understand, thank you.

• We're not here to do your homework. – orlp Dec 16 '18 at 4:46
• its not a homework – JKLM Dec 16 '18 at 4:57

## 1 Answer

It'll be hard to understand numbers 3 and 4 until you're solid on the others. I'd suggest looking closely at the definition of recursion. A solid understanding of recursion is crucial to a lot of computer science.

But for answers, if it helps at all:

Can we use recursive algorithm to find the greatest element of a finite list when numbers are unsorted.

def greatest(list):
first = list[0]
remaining = list[1:]
if remaining exists:
return max(first, greatest(remaining))
else:
return first


How to use recursive algorithm to find the least element of a finite list of unsorted numbers where repetitions of number is allowed.

Exactly the same as above, but use min instead of max.

How can Mergesort calls itself n^2 times on a list with n numbers.

It doesn't. Mergesort runs in $$O(n \log n)$$. Are you thinking of Quicksort?

Is it true if the input list has only 3 numbers, then Mergesort does not need the merging step.

Depends on your implementation. The simple cases of algorithms, when $$n$$ is so far, tend not to be interesting—but have a lot of potential for bugs. So if I were writing Mergesort, I'd start with something like "if you have less than five numbers, do it by brute force (which is $$O(1)$$ since we have an upper bound on $$n$$)".

Can we find number of elements in a finite list with a recursive algorithm.

def count_elements(list):
if list does not exist: return 0
return 1 + count_elements(list[1:])

• Thank you, so for 4th point, it's not true unless you use brute force? – JKLM Dec 16 '18 at 16:40
• @JKLM It depends on your implementation. If I were implementing it, I'd use brute force for that particular case. Others might do it differently. – Draconis Dec 16 '18 at 16:53
• so theroticallly it does not need that merging step? – JKLM Dec 16 '18 at 17:03
• @JKLM Again, it depends on your implementation. Some implementations would use a merging step there, while others wouldn't. – Draconis Dec 16 '18 at 17:22