bsort(field A, int l, int r) {
  root:= null;
  for i:= r downto l do {
    top:= insert(A, root, new node_element(i));
    if (top <> null) {
      root:= new node_head(1, root, top);
    }
  }
  resolve(A, B, l, root);
  for i:= l to r do {
    A[i]:= B[i];
  }
}

node_element insert(field A, node_head head, node_element e) {
  if (head <> null) then {
    prev:= find_ge(A, head, e);
    e:= insert(A, prev.child, e);
    if (e <> null) then {
      e.next   := prev.next;
      prev.next:= e;
      head.count++;
      if (head.count > 2*k) then {
        e:= split(head);
      } else {
        e:= null;
      }
    }
  }
  return e;
}

int resolve(field A, field B, int index, node_head head) {
  if (head <> null) then {
    current:= head;
    while (current <> null) do {
      index:= resolve(A, B, index, current.child);
      if (current.next <> null) then {
        B[index]:= A[current.next.index];        
        index++;
      }
      current:= current.next;
    }
  }
  return index;
}


node find_ge(field A, node_head head, node_element e) {
  prev:= head;
  while ((prev.next <> null) and (A[e.index] > A[prev.next.index])) do {
    prev:= prev.next;
  }
  return prev;
}

node find_n(node_head head, int i) {
  prev:= head;
  j:= 0;
  while (j < i) do {
    prev = prev.next;
    j++;
  }
  return prev;
}

node_element split(node_head head) {
  prev        := find_n(head, k);
  parent      := prev.next;
  prev.next   := null;
  head.count  := k;
  parent.child:= new node_head(k, parent.child, parent.next);
  parent.next := null;
  return parent;
}

private abstract class node {
  public node_element next;
  public node_head    child;
}

protected class node_element extends node {
  public int index;
  public node_element(int index) {
    this.index = index;
    this.child = null;
    this.next  = null;
  }
}

protected class node_head extends node {
  public int count;
  public node_head(int count, node_head child, node_element first) {
    this.count = count;
    this.child = child;
    this.next  = first;
  }
}