STACK_EMPTY(S)
  if(s.top == 0)
    return true
  return false
  
PUSH(S, x)
  S.top += 1
  S[S.top] = x


POP(S)
  if(STACK_EMPTY(S))
    error "stack underflow"
  else 
    S.top -= 1
    return S[S.top+1]

head = 0
tail = 1
ENQUEUE(Q, x)
  Q[tail] = x
  if(tail == Q.length)
    tail = 1
  else 
    Q.tail += 1
  
DEQUEUE(Q)
  x = Q[head]
  if(Q.head == Q.length)
    Q.head = 1
  else 
    Q.head += 1
    return x 
    

LEFT(i)
  return 2 * i
RIGHT(i)
  return 2 * i + 1
PARENT(i)
  return i/2
  
MAX-HEAPIFY(A, i)
  l = LEFT(i)
  r = RIGHT(i)
  // largest = max(i, l, r)
  if(l <= A.heap_size && A[i] < A[l])
    largest = l
  else
    largest = i
  if(r <= A.heap_size && A[max] < A[r])
    largest = r
  if(max != i)
    swap(A[largest], A[i])
    MAX-HEAPIFY(A, largest)
  
BUILD-MAX-HEAP(A)
  for(i = A.heap_size / 2; i >=1; i--)
    MAX-HEAPIFY(A, i)

HEAP-MAXIMUM(A)
  return A[1]

HEAP-EXTRACT-MAX(A)
  if(A.heap_size < 1)
    error "heapsize underflow"
  max = A[1]
  A[1] = A[A.heap_size]
  A.heap_size -= 1
  MAX-HEAPIFY(A,1)
  return max
  
HEAP-INCREASE-KEY(A, i, key)
  A[i] = key
  while(i>1 && A[PARENT(i)] < A[i])
    swap(A[PARENT(i)], A[i])
    i = PARENT(i)

MAX-HEAP-INSERT(A, key)
  A.heap_size += 1
  A[A.heap_size] = INT.MIN
  HEAP-INCREASE-KEY(A, A.heap_size, key)

HEAPSORT(A)
  BUILD_HEAP(A)
  for(i = A.length; i >=2; i--)
    swap(A[1], A[i])
    A.heap_size--
    MAX-HEAPIFY(A, 1)

PARTITION(A, p, r)
  x = a[r]
  i = p-1
  for(j = p; j< r; j++)
    if(A[j] < x)
      i++
      swap(A[i], A[j])
  swap(A[i+1], A[r])
  return i+1
  

QUICKSORT(A, p, r)
  if(p<r)
    q = PARTITION(A, p, r)
    QUICKSORT(A, p, q-1)
    QUICKSORT(A, q+1, r)
    
QUICKSORT(A, 1, A.length)

MERGE-SORT(A, p, r)
  if(p < r)
    q = p + (r - p) /2
    MERGE-SORT(A, p, q)
    MERGE-SORT(A, q+1, r)
    MERGE(A, p, q, r)

MERGE(A, p, q, r)
  n1 = q - p + 1
  n2 = r - q
  L = new int[n1]
  R = new int[n2]
  for i = 1 to n1
    L[i] = A[p+i-1]
  for j = 1 to n2
    R[j] = A[q+j]
  i = 1
  j = 1  
  for k = p to r
    if(L[i] <= R[j]
      A[k] = L[i]
      i = i+1
    else 
      A[k] = R[j]
      j = j+1

COUNTING-SORT(A, B, k)
  C = new int[k+1]
  // B = new int[A.length]
  for i = 0 to k
    C[i] = 0
  for j = 1 to A.length
    C[A[i]] = C[A[j]] + 1
  for i = 1 to k
    C[i] = C[i-1] + C[i] 
  for j = A.length to 1
    B[C[A[j]]] = A[j]
    C[A[j]] = C[A[j]] - 1

RADIX-SORT(A, d)
  for i = 1 to d  // from the least significant bit to most significant bit
    use a stable sort to sort array A on digit i

BUCKET-SORT(A)
  n = A.length
  B = new double[n] 
  for i = 1 to n
    let B[i] an empty list
  
  for i = 1 to n
    insert A[i] into list B[n*A[i]] by INSERTION SORT
  for i = 1 to n
    sort list B[i] with INSERTION SORT
  CONCATENATE THE LISTS B[1] ... B[n] TOGETHER IN ORDER