Sort Integers II – Python 3 ( Week 18 – 07)

class Solution:
    """
    @param A: an integer array
    @return: nothing
    """
    def sortIntegers2(self, A):
        # write your code here
        self.quickSort(A, 0, len(A) - 1)
    
    def quickSort(self, A, start, end):
        if start >= end:
            return
    
        left, right = start, end
        pivot = A[(start + end) // 2]
        while left <= right:
            while left <= right and A[left] < pivot:
                left += 1
            while left <= right and A[right] > pivot:
                right -= 1
                
            if left <= right:
                A[left], A[right] = A[right], A[left]
                left += 1
                right -= 1
    
        self.quickSort(A, start, right)
        self.quickSort(A, left, end)

class Solution:
    """
    @param A: an integer array
    @return: nothing
    """
    def sortIntegers2(self, A):
        # write your code here
        if len(A) <= 1:
            return A
            
        temp = [0] * len(A)
        self.mergeSort(A, 0, len(A) - 1, temp)
    
    def mergeSort(self, A, start, end, temp):
        if start >= end:
            return
        self.mergeSort(A, start, (start + end) // 2, temp)
        self.mergeSort(A, (start + end) // 2 + 1, end, temp)
        self.merge(A, start, end, temp)
    
    def merge(self, A, start, end, temp):
        index, left, middle, right = start, start, (start + end) // 2, (start + end) // 2 + 1
        
        while left <= middle and right <= end:
            if A[left] <= A[right]:
                temp[index] = A[left]
                index += 1
                left += 1
            else:
                temp[index] = A[right]
                index += 1
                right += 1
                
    
        while left <= middle:
            temp[index] = A[left]
            index += 1
            left += 1
        
        while right <= end:
            temp[index] = A[right]
            index += 1
            right += 1
            
        for i in range(start, end + 1):
            A[i] = temp[i]