1)Write a program implementing the following modification of mergesort: split
the sequence in three roughly equal parts, recursively sort each part, and
then merge the three parts. Compare the performance of this with the
mergesort done in the class. To compare, you will need to generate a very
large sequence.


2)Write a recursive version of insertion sort. Notice that insertion sort on n elements is equivalent to insertion sort on n-1 elements followed by inserting the nth element in the proper position. Use your program to sort an array of 10 numbers.

3)
There is a ladder consisting of n horizontal bars, each pair of consecutive bars are separated
by a distance of 1 feet. A person is standing at the bottom of the ladder. He/She may
either climb 1 bar, 2 bar or 3 bars in a single step. Print all ways of reaching the top of
the ladder. You should also return the total number of ways of climbing the ladder. The
value of n is provided from command line. For example, if n = 4, the answer should be:

There are total 7 ways :
-1-1-1-1
-1-1-2
-1-2-1
-1-3
-2-1-1
-2-2
-3-1