import errors

# Recursive merge sort algorithm
# https://rosettacode.org/wiki/Sorting_algorithms/Merge_sort#Python
def merge(x, y, i):
    if x == []:
        return y
    if y == []:
        return x
    return (
        [x[0]] + merge(x[1:], y, i)
        if x[0][i] < y[0][i]
        else [y[0]] + merge(x, y[1:], i)
    )


def sort(a, n, i):
    m = n // 2
    return (
        a
        if n <= 1
        else merge(sort(a[:m], m, i), sort(a[m:], n - m, i), i)
    )


class dictionary:
    def __init__(self):
        self.data = []
        self.size = 0

    def add(self, key, value):
        if type(value) != int:
            self.data.append([key, value])
            self.size += 1

    # increment a value
    def inc(self, key, value=1):
        # defensive programming
        in_data = False
        i = 0
        # high efficiency loop stops after found
        while i < self.size and in_data == False:
            if self.data[i][0] == key:
                self.data[i][1] += value
                in_data = True
            i += 1
        if not in_data:
            self.add(key, value)

    # Sort dictionary by value
    def sort_by_value(self):
        self.data = sort_v(self.data, self.size, 1)