Sort Algorithm 3 - Merge Sort

Array

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))

(1) average cost time: T(n) = O(nlogn)
(2) average cost space: S(n) = O(n)
(3) Not in-place sort
(4) stable
(5) best T(n) = O(nlogn), worst T(n) = O(nlogn)

Linked List

lc 148: Given the head of a linked list, return the list after sorting it in ascending order.

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))

(1) average cost time: T(n) = O(nlogn)
(2) average cost space: S(n) = O(1)
(3) in-place
(4) stable
(5) best T(n) = O(nlogn), worst T(n) = O(nlogn)