Burj Lizi X

def mergeSort(nums):
    if len(nums) <= 1: return nums
    # devide
    mid = len(nums)//2
    left = nums[:mid]
    right = nums[mid:]
    return mergeFunc(mergeSort(left),mergeSort(right))

def mergeFunc(left,right):
    # merge
    res = []
    while left and right:
        if left[0] <= right[0]:
            res.append(left.pop(0))
        else:
            res.append(right.pop(0))
    res += left
    res += right

    return res

if __name__ == "__main__":
    nums = [10, 17, 50, 7, 30, 24, 30, 45, 15, 5, 36, 21]
    print(mergeSort(nums))

def sortList(head):
    if not head or not head.next: return head
    # get mid of linked list
    slow = fast = head
    while fast and fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    # devide 
    right = slow.next
    slow.next = None
    
    # merge
    def mergeFunc(head,right):
        dummy = ListNode()
        cur = dummy
        while head and right:
            if head.val <= right.val:
                cur.next = head
                head = head.next
                # cur = cur.next
                # cur.next = None               
            else:
                cur.next = right
                right = right.next
            cur = cur.next
            cur.next = None
        if head:
            cur.next = head
        if right:
            cur.next = right
        return dummy.next

    return mergeFunc(sortList(head),sortList(right))

def solution(nums):
    low, high = 0, len(nums)-1
    quickSort(nums,low,high)
    return nums

def quickSort(nums,low,high):
    if low < high:
        pivotpos = partition(nums,low,high)
        quickSort(nums,low,pivotpos-1)
        quickSort(nums,pivotpos+1,high)

def partition(nums,low,high):
    pivot = nums[low]
    while low < high:
        while low < high and nums[high] >= pivot:
            high -= 1
        nums[low] = nums[high]
        while low < high and nums[low] <= pivot:
            low += 1
        nums[high] = nums[low]
    nums[low] = pivot
    return low


if __name__ == "__main__":
    nums = [10, 17, 50, 7, 30, 24, 30, 45, 15, 5, 36, 21]
    print(solution(nums))

def bubbleSort(nums):
    for i in range(len(nums)-1):
        for j in range(len(nums)-1-i):
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
    return nums
if __name__ == '__main__':
    nums = [10, 17, 50, 7, 30, 24, 30, 45, 15, 5, 36, 21]
    print(bubbleSort(nums))