Insertion Sort

Key Idea

This is probably the most intuitive sorting algorithm. If you have played poker before, then this is your go-to algorithm to sort cards in your hand.

Brute Force

def sortIntegers(A: List[int]) -> List[int]:
    
    n = len(A)
    
    if n == 0:
        return 
    
    sorted_list = [] 
    
    for num in A:
        i = find_insert_position(sorted_list, num)
        sorted_list.insert(i, num)
    
    return sorted_list
    
def find_insert_position(sorted_list: List[int], num: int) -> int:

  n = len(sorted_list)

  if n == 0:
      return 0 

  for i in range(n):
      if sorted_list[i] > num:
          return i

  return n

time O(n^2) space O(n)

  def sortIntegers2(self, A: List[int]) -> None:
      
      n = len(A)
      
      if n == 0:
          return 
      
      sorted_list = [] 
      
      for num in A:
          i = bisect.bisect_left(sorted_list, num)
          sorted_list.insert(i, num)

      return sorted_list 

Insertion takes O(n) because copying the array but finding the inserting position is only O(logn) now

Code

need to swap for in-place operations

def sortIntegers(A: List[int]) -> None:
    
    n = len(A)
    
    if n == 0:
        return 
    
    for i in range(n):
        # expand sorted list to index i 
        insert(A, i)

        
def insert(nums: List[int], i: int) -> None:
    
    j = i 
    
    for j in range(i, 0, -1):
        if nums[j] < nums[j-1]:
            swap(nums, j, j-1)
        else:
            break


def swap(nums: List[int], i: int, j: int) -> None:
    temp = nums[i]
    nums[i] = nums[j] 
    nums[j] = temp 

public void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        // all cards before i are sorted
        insert(arr, i);
    }
}

private void insert(int[] arr, int newbie) {
    for (int i = newbie; i > 0 && arr[i] < arr[i-1]; i--) {
        swap(arr, i, i-1);
    }
}

Time Complexity

The worst case analysis in bubble sort, selection sort, and insertion sort all share a common theme - a halved square (a rugged triangle). That triangle is proportional to O(n^2).