Algorithm Post: Divide and Conquer - Merge Sort and Quick Sort

mergesort_quicksort.py

class QuickSort:
    def sort(self, arr):
        self.qsort(arr, 0, len(arr) - 1)
        return arr

    def qsort(self, arr, st, ed):
        if st >= ed:
            return

        index = self.partition(arr, st, ed)
        self.qsort(arr, st, index - 1)
        self.qsort(arr, index + 1, ed)

    def partition(self, arr, st, ed):
        pivot = arr[st]
        i, j = st, ed
        while i <= j:
            while i <= j and arr[i] <= pivot:
                i += 1
            while i <= j and arr[j] > pivot:
                j -= 1
            if i <= j:
                arr[i], arr[j] = arr[j], arr[i]
                i += 1
                j -= 1
        arr[st], arr[j] = arr[j], arr[st]
        return j


class MergeSort:
    def sort(self, arr):
        if not arr or len(arr) == 1:
            return arr
        mid = len(arr) / 2
        left = self.sort(arr[:mid])
        right = self.sort(arr[mid:])
        return self.merge(left, right)

    def merge(self, left, right):
        len_l, len_r = len(left), len(right)
        temp = [None] * (len_l + len_r)
        i = l = r = 0
        while l < len_l or r < len_r:
            vl = left[l] if l < len_l else 2**31
            vr = right[r] if r < len_r else 2**31
            if vl < vr:
                temp[i] = vl
                l += 1
            else:
                temp[i] = vr
                r += 1
            i += 1
        return temp


if __name__ == '__main__':
    arr = [5, 1, 3, 2, 4, 3, 3, 3, 2, 1, 5]
    print(QuickSort().sort(arr))
    arr = [5, 1, 3, 2, 4, 3, 3, 3, 2, 1, 5]
    print(MergeSort().sort(arr))