Sort summary

Algorithm	Time Complexity			Space Complexity
	Best	Average	Worst	Worst
Quicksort	Ω(n log(n))	Θ(n log(n))	O(n^2)	O(log(n))
Mergesort	Ω(n log(n))	Θ(n log(n))	O(n log(n))	O(n)

class Solution(object):
    def sortIntegers1(self, A):
        # merge sort
        # https://www.geeksforgeeks.org/merge-sort/
        def merge(left, right):
            llen, rlen = len(left), len(right)
            l, r = 0, 0
            result = []
            while l < llen and r < rlen:
                if left[l] <= right[r]:
                    result.append(left[l])
                    l += 1
                else:
                    result.append(right[r])
                    r += 1
            result += left[l:]
            result += right[r:]
            return result

        Alen = len(A)
        if Alen < 2:
            return A
        mid = Alen / 2
        left = self.sortIntegers1(A[:mid])
        right = self.sortIntegers1(A[mid:])
        return merge(left , right)

    def sortIntegers2(self, A):
        # quick sort
        # https://www.geeksforgeeks.org/quick-sort/
        if len(A) < 2:
            return A
        left, right = [], []
        pivot = A.pop()

        for x in A:
            if x <= pivot:
                left.append(x)
            else:
                right.append(x)

        return self.sortIntegers2(left) + [pivot] + self.sortIntegers2(right)

    def sortIntegers3(self, A):
        # bubble sort
        for i in range(len(A)):
            for j in range(len(A)-1):
                if A[j] > A[j + 1]:
                    A[j], A[j + 1 ] = A[j + 1], A[j]
        return A


print Solution().sortIntegers1([4, 5, 3, 2, 4, 2, 1]) # merge sort
print Solution().sortIntegers2([4, 5, 3, 2, 4, 2, 1]) # quick sort
print Solution().sortIntegers3([4, 5, 3, 2, 4, 2, 1]) # bubble sort