class Sort(object):
    def quick_sort(self, ls):
        self.quick_sort_helper(ls, 0, len(ls) - 1)
        return ls

    def quick_sort_helper(self, ls, start, end):
        if end <= start:
            return
        pivot_index = random.randint(start, end)
        pivot = ls[pivot_index]  # pivot value
        ls[pivot_index], ls[end] = ls[end], ls[pivot_index]  # swap with the value in index end.
        boundary = start  # boundary is in index start.
        for i in range(start, end):
            if ls[i] < pivot:
                ls[i], ls[boundary] = ls[boundary], ls[i]  # swap with the value in index i.
                boundary += 1
        ls[boundary], ls[end] = ls[end], ls[boundary]  # lie the pivot in index boundary.
        self.quick_sort_helper(ls, start, boundary - 1)
        self.quick_sort_helper(ls, boundary + 1, end)

    def merge_sort(self, ls):
        buffer = ls[:]
        self.merge_sort_helper(ls, buffer, 0, len(ls) - 1)
        return ls

    def merge_sort_helper(self, ls, buffer, start, end):
        if end <= start:
            return
        middle = (start + end) // 2
        self.merge_sort_helper(ls, buffer, start, middle)
        self.merge_sort_helper(ls, buffer, middle + 1, end)
        i1, i2 = start, middle + 1
        for i in range(start, end+1):
            if i2 > end:
                buffer[i] = ls[i1]
                i1 += 1
            elif i1 > middle:
                buffer[i] = ls[i2]
                i2 += 1
            elif ls[i1] < ls[i2]:
                buffer[i] = ls[i1]
                i1 += 1
            else:
                buffer[i] = ls[i2]
                i2 += 1
        ls[start:end+1] = buffer[start:end+1]

if __name__ == '__main__':
    ls = [1, 9, 5, 4, 3, 7, 6]
    s = Sort()
    print(s.quick_sort(ls[:]))
    print(s.merge_sort(ls[:]))