typedef struct vc_frame  
{  
  char res_pt;  
  int start;  
  int end;  
} vc_frame;  
 
#define SWAP(arr, i, j) {int t; t = arr[i]; arr[i] = arr[j]; arr[j] = t;}  
 
void quick_sort(int start, int end, int *arr)  
{  
  int pivot_loc, pivot;  
  int i, j;  
 
  pivot_loc = (start+end)/2;  
  pivot = arr[pivot_loc];  
 
  SWAP(arr, start, pivot_loc);  
 
  i = start+1;  
  j = end;  
 
  while(1)  
  {  
    while(i <= end && arr[i] <= pivot)  
      i++;  
 
    while(j >= start+1 && arr[j] > pivot)  
      j--;  
 
    if(i < j)  
      SWAP(arr, i, j)  
    else  
      break;  
  }  
 
  SWAP(arr, start, i-1);  
 
  /* Recursion: sort the left partition */  
  if(start < i-2)  
    quick_sort(start, i-2, arr);  
 
  /* Recursion: sort the right partition */  
  if(i < end)  
    quick_sort(i, end, arr);  
}

void quick_sort_stack(int start, int end, int *arr)  
{  
  vc_frame vc_stack[10000];  
  int top;  
 
  /* Setup the frame for initial virtual-call. */  
  vc_stack[0].res_pt = 0;  
  vc_stack[0].start = start;  
  vc_stack[0].end = end;  
  top = 0;  
 
  while(top >= 0)  
  {  
    /* Read the topmost frame from vc_stack.*/  
    vc_frame *curr = &vc_stack[top];  
    int s = curr->start;  
    int e = curr->end;  
 
    switch(curr->res_pt)  
    {  
      case 0:  
      {  
        /* This code portion is simply copied from quick_sort(): START */  
        /* The local variables required only in this code-block... */  
        int pivot_loc, pivot;  
        int i, j;  
 
        pivot_loc = (s+e)/2;  
        pivot = arr[pivot_loc];  
 
        SWAP(arr, s, pivot_loc);  
 
        i = s+1;  
        j = e;  
 
        while(1)  
        {  
          while(i <= e && arr[i] <= pivot)  
            i++;  
 
          while(j >= s+1 && arr[j] > pivot)  
            j--;  
 
          if(i < j)  
            SWAP(arr, i, j)  
          else  
            break;  
        }  
 
        SWAP(arr, s, i-1);  
        /* This code portion is simply copied from quick_sort(): END */  
 
        if(s < i-2)  
        {  
          /* Recursion: sort the left partition. Push a new frame on  
             vc_stack. */  
          vc_stack[top+1].start = s;  
          vc_stack[top+1].end = i-2;  
          vc_stack[top+1].res_pt = 0;  
          top++;  
        }  
 
        /* Use curr’s start/end to store the range of right partition,  
           to use upon resuming this call. */  
        curr->start = i;  
        curr->end = e;  
        curr->res_pt = 1;  
        break;  
      }  
 
      case 1:  
      {  
        /* The earlier value of ’i’ was saved in curr->start. */  
        int i = s;  
 
        if(i < e)  
        {  
          /* Recursion: sort the right partition. Push a new frame on  
             vc_stack. */  
          vc_stack[top+1].start = i;  
          vc_stack[top+1].end = e;  
          vc_stack[top+1].res_pt = 0;  
          top++;  
        }  
 
        curr->res_pt = 2;  
        break;  
      }  
 
      case 2:  
      {  
        /* Pop the current frame from vc_stack. */  
        top--;  
        break;  
      }  
    }  
  }  
}