leetcode-sorting

insertionSort.py

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        return self.insertionSort(nums)

    def insertionSort(self, A):
        """
        Idea is think of array as two sections given index j:
            On the left side of j, it's partial sorted array.
            On the right side of j, it's unsorted array.
        [5,2,3,1]
         i
         j
           i  
           j  -> [2,5,3,1]
         j
         [2,5,3,1]
              i
              j -> [2,3,5,1]
              i
            j
        <-----x--->
  sorted area   unsorted area
        T: O(n^2) for worst and average time complexity. Best complexity is O(n) when array is sorted already.
        S: O(1) because we don't use extra space.
        """
        n = len(A)
        for i in range(n):
            # On the left side of j, it's partial sorted array. Contrarily, on the right side of j, it's unsorted array.
            j = i 
            while j > 0 and A[j-1] > A[j]:
                A[j], A[j-1] = A[j-1], A[j]
                j -= 1
        return A