Sort Merge Quick Heap

Sort Merge Quick Heap.py

class Solution:
    """BEST"""
    def merge(self, li1, li2):
        
        merged = []
        i, j = 0, 0
        
        while i < len(li1) and j < len(li2):
            if li1[i] <= li2[j]:
                merged.append(li1[i])
                i += 1
            else:
                merged.append(li2[j])
                j += 1
        
        return merged + li1[i:] + li2[j:]  # Pay attention here it's [i:] & [:j]

    def driver(self, arr):
        if len(arr) < 2:
            return arr

        mid = len(arr) // 2
        return self.merge(
            self.driver(arr[:mid]),
            self.driver(arr[mid:]),
        )


arr = [-2, -4, 44, 90, 120, 132, 0, 3]
obj = Solution()
ans = obj.driver(arr)
print(ans)



# ............................Quick Sort.........................................
class QuickSort:
    """
    Most Accepted Solution
    pivot as mid
    """
    def driver(self, nums: list) -> list:
        if not nums:
            return nums
        self.quick_sort(0, len(nums) - 1, nums)
        return nums

    def quick_sort(self, start, end, nums):
        if start >= end:
            return

        left, right = start, end
        pivot = nums[(left + right) // 2]

        while left <= right:

            while left <= right and nums[left] < pivot:
                left += 1

            while left <= right and nums[right] > pivot:
                right -= 1

            if left <= right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1

        self.quick_sort(start, right, nums)
        self.quick_sort(left, end, nums)

# Quick_sort range <start-----left------p------right------end>

# .............................HEAP SORT............................
class HeapSort:
    def heapify(self, arr, n, i):
        parent = i
        l = 2*i + 1
        r = 2*i + 2

        if l < n and arr[l] > arr[parent]:
            parent = l
        if r < n and arr[r] > arr[parent]:
            parent = r
        if parent != i:
            arr[parent], arr[i] = arr[i], arr[parent]
            self.heapify(arr, n, parent)

    def driver(self, arr):
        n = len(arr)
        for i in range(n // 2 - 1, -1, -1):
            self.heapify(arr, n, i)
        for j in range(n - 1, 0, -1):
            arr[0], arr[j] = arr[j], arr[0]
            self.heapify(arr, j, 0)
        return arr


arr = [-2, -4, 44, 90, 1, 120, 132, 0, 3]
hs = HeapSort()
ans = hs.driver(arr)
print(ans)