part(list, left, right, pivotIndex)={
  my(pivotValue=list[pivotIndex],storeIndex=left,t);
  t=list[pivotIndex];
  list[pivotIndex]=list[right];
  list[right]=t;
  for(i=left,right-1,
    if(list[i] <= pivotValue,
      t=list[storeIndex];
      list[storeIndex]=list[i];
      list[i]=t;
      storeIndex++
    )
  );
  t=list[right];
  list[right]=list[storeIndex];
  list[storeIndex]=t;
  storeIndex
};
quickselect(list, left, right, n)={
  if(left==right,return(list[left]));
  my(pivotIndex=part(list, left, right, random(right-left)+left));
  if(pivotIndex==n,return(list[n]));
  if(n < pivotIndex,
    quickselect(list, left, pivotIndex - 1, n)
  ,
    quickselect(list, pivotIndex + 1, right, n)
  )
};