# def merge_sort left right None if right is None right len if right lef

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62``` ```def merge_sort(a, left=0, right=None): if right is None: right = len(a) if right - left > 1: middle = (left + right) // 2 merge_sort(a, left, middle) merge_sort(a, middle, right) merge(a, left, middle, right) def merge(a, left, middle, right): first = a[left:middle] second = a[middle:right] i = j = 0 for k in range(left, right): if i < len(first) and (j == len(second) or first[i] <= second[j]): a[k] = first[i] i += 1 else: a[k] = second[j] j += 1 def bisect_right(a, x): left, right = 0, len(a) # [left; right) while right - left > 1: # until [left, right) == {x} assert (x not in a) or (x in a[left:right]) mid = (left + right) // 2 print(mid) if a[mid] <= x: left = mid else: right = mid if a[left] == x: # why not m? return left else: return None def bisect_left(a, x): left, right = -1, len(a) - 1 # (left; right] while right - left > 1: # until (left, right] == {x} #assert (x not in a) or (x in a[left+1:right+1]) # x in (left; right] mid = (left + right) // 2 print(mid) if a[mid] < x: left = mid else: right = mid print(right) if a[right] == x: # why not m? return right else: return None a = [3, 4, 5, 6, 8, 7, 9, 10] print(bisect_left(a, 8)) #a = [1, 3, 4, 4, 4, 5, 6, 6] #print(bisect_right(a, 4)) ```