Important algorithms for interviews

algo.py

def mergeSort(A):
  mid = len(A) // 2
  if len(A) > 1:
    left = mergeSort(A[:mid])
    right = mergeSort(A[mid:])
    
  # merge
  i = j = k = 0
  while i  < len(left) and j < len(right):
    if left[i] < right[j]:
      A[k] = left[i]
      i += 1
    else:
      A[k] = right[j]
      j += 1
    k += 1
    
    while i < len(left):
      A[k] = left[i]
      i += 1
      k += 1
      
      
    while j < len(right):
      A[k] = right[j]
      j += 1
      k += 1
     
  return A
    
def partition(A, first, last):
  pivot = A[last]
  
  lefti = first + 1
  righti = last
    
  done = False
  while not done:
    while lefti <= righti and A[lefti] <= pivot:
      lefti += 1
    
    while A[righti] >= pivot and righti >= lefti:
      righti -= 1
    
    if righti < lefti:
      done =True
    else:
      temp = A[lefti]
      A[lefti] = A[righti]
      A[righti] = temp
  temp = A[lefti]
  A[lefti] = A[righti]
  A[righti] = temp
  
  return righti
  

def quickSortHelper(A, left, right):
  if left < right:
    ind = partition(A, left, right)
    
    quickSortHelper(A, left, ind - 1)
    quickSortHelper(A, i + 1, right)

def quickSort(A):
  return quickSortHelper(A, 0, len(A) - 1)

def BFS(G):
  pass

def DFS(G):
  pass

def binarySearch(A, x):
  pass