Interview Question 5: Sorting Algorithms

class QuickSort:

    def quick_sort(self, arr):
        if len(arr) > 0:
            self.sort(arr, 0, len(arr) - 1)
        else:
            print('ERROR: input array is empty!')
        print(arr)
    
    def sort(self, arr, left, right):
        if left < right:
            partition_key = self.partition(arr, left, right)
            
            self.sort(arr, partition_key + 1, right)
            self.sort(arr, left, partition_key - 1)

    # Result:
    #   (smaller values), arr[wall], (bigger values)
    # Return `wall` as the new partition_key. 
    def partition(self, arr, left, right):
        pivot = arr[right]
        wall = left
        
        for i in range(left, right):
            if arr[i] < pivot:
                self.swap(arr, i, wall)
                wall += 1
        self.swap(arr, wall, right)
        return wall

    def swap(self, arr, left, right):
        tmp = arr[left]
        arr[left] = arr[right]
        arr[right] = tmp

def mergeSort(arr, left, right):
    if left < right:
        mid = left + (right - left) // 2

        mergeSort(arr, left, mid)
        mergeSort(arr, mid + 1, rright)
        
        merge(arr, left, mid, right)