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[:]))