written 22 months ago by |
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.
The function merge sort will sort the list from indexes from start to end – 1 inclusive.
If the end – the start is not greater than 1, then return.
Otherwise, set mid equal to the floor of (start + end)/2.
Call merge sort with the same list and with start = start and end = mid as arguments.
Call the function merge list, passing the list and the variables start, mid, and end as arguments.
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: