Merge sort is a recursive sorting algorithm and it's quite a bit faster than bubble sort. It's a divide and conquer algorithm.:
In merge sort we:
Click to play video
The algorithm consists of two separate functions, merge_sort() and merge().
merge_sort() divides the input array into two halves, calls itself on each half, and then merges the two sorted halves back together in order.
The merge() function merges two already sorted lists back into a single sorted list. At the lowest level of recursion, the two "sorted" lists will each only have one element. Those single element lists will be merged into a sorted list of length two, and we can build from there.
In other words, all the "real" sorting happens in the merge() function.
Input: A, an unsorted list of integers
A is less than 2, it's already sorted so return itmerge_sort() twice, once on each halfsorted_left_side, sorted_right_side) on the results of the merge_sort() callsInputs: A and B. Two sorted lists of integers
final list of integers.i and j equal to zero. They will be used to keep track of indexes in the input lists (A and B).A and B. If an element in A is less than or equal to its respective element in B, add it to the final list and increment i. Otherwise, add the item in B to the final list and increment j. Continue until all items from one of the lists have been added.A or B. Add those extra items to the final list.Our LockedIn influencers are complaining that when they sort their followers by follower count, it gets really slow if they have more than 1,000 followers (because we're using Bubble Sort). Let's speed it up for them with merge sort.
Complete the merge_sort and merge functions according to the described algorithms.