June 2018
Beginner
508 pages
13h 8m
English
Let's see how all this translates into code, starting by learning how to code our own homemade mergesort:
# ms/algo/mergesort.pydef sort(v): if len(v) <= 1: return v mid = len(v) // 2 v1, v2 = sort(v[:mid]), sort(v[mid:]) return merge(v1, v2)def merge(v1, v2): v = [] h = k = 0 len_v1, len_v2 = len(v1), len(v2) while h < len_v1 or k < len_v2: if k == len_v2 or (h < len_v1 and v1[h] < v2[k]): v.append(v1[h]) h += 1 else: v.append(v2[k]) k += 1 return v
Let's start from the sort function. First we encounter the base of the recursion, which says that if the list has 0 or 1 elements, we don't need to sort it, we can simply return it as it is. If that is not the case, then we calculate the midpoint (mid), and recursively ...
Read now
Unlock full access