mergesort.md

Code

Array not inplace

better done with linked list

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def merge_sort(nums_list, start, end):
            if (start == end):
                return [nums_list[start]]
            mid = ((end + 1 - start) // 2) + start
            left = merge_sort(nums_list, start, mid-1)
            right = merge_sort(nums_list, mid, end)
            
            # merge, compare left and right
            ans = []
            while left and right:
                ans.append(left.pop(0)) if left[0] <= right[0] else ans.append(right.pop(0))
            
            # add leftovers that are already sorted
            ans.extend(left)
            ans.extend(right)
            return ans
            
        return merge_sort(nums, 0, len(nums)-1)

Array in place

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def shift_right(nums_list, start, end):
            while end > start:
                nums_list[end] = nums_list[end-1]
                end -=1
            return nums_list
            
        def merge_sort(nums_list, start, end):
            if (start >= end):
                return start, end
            mid = ((end + 1 - start) // 2) + start
            left_s, left_e = merge_sort(nums_list, start, mid-1)
            right_s, right_e = merge_sort(nums_list, mid, end)
            
            # merge, compare left and right, if right smaller then left insert before start of left, the sorted portion.
            os = left_s
            while left_s <= left_e and right_s <= right_e:
                if nums_list[right_s] < nums_list[left_s]:
                    tmp = nums_list[right_s]
                    nums_list = shift_right(nums_list, left_s, right_s)
                    nums_list[left_s] = tmp
                    left_s += 1
                    left_e += 1
                    right_s += 1
                else:
                    left_s += 1
            return os, right_e
            
        merge_sort(nums, 0, len(nums)-1)
        return nums