Solution:

Merge sort is one of the most important sorting algorithms based on the divide and conquer technique.

Merge sort is very popular for its efficiency to sort the data in a small amount of time. It is one of the best examples of applications for divide and conquers algorithms.

Algorithm:

Create a function merge sort that takes a list and two variables start and end as arguments.

1. The function merge sort will sort the list from indexes from start to end – 1 inclusive.

2. If the end – the start is not greater than 1, then return.

3. Otherwise, set mid equal to the floor of (start + end)/2.

4. Call merge sort with the same list and with start = start and end = mid as arguments.

5. Call the function merge list, passing the list and the variables start, mid, and end as arguments.

6. The function merge list takes a list and three numbers, start, mid, and end as arguments and assuming the list is sorted from indexes start to mid – 1 and from mid to end – 1, merges them to create a new sorted list from indexes from start to end – 1.

Input:

Output: