Merge Sort

A recursive sorting algorithm where elements are divided into 2 halves. The function will call itself on both halves, followed by a merge function to merge the 2 sorted halves.
Best Time Complexity: O(nlogn)
Worse Time Complexity: O(nlogn)

Usage

merge_sort(lst:list, key:Callable = lambda x:x, visualise:bool = False, animate:bool = False)

Parameters:
      lst : List
            A list of elements to be sorted
      key : Callable
            A custom function on how the elements should be sorted
      visualise : Boolean
            If true, the generator object will record the state of the list after each iteration
      animate : Boolean
            If true, the generator object will record each change in the state of the list

Returns:
      List
            A list of state changes that happened to the list

Comments

1. This function does not print or perform animations. Find out how to do that here.

Example

from jellybeans.algos import merge_sortlst = [9, 19, 1, 17, 6, 20, 4, 13, 15, 3]merge_sort(lst)print(lst) # [1, 3, 4, 6, 9, 13, 15, 17, 19, 20]