Help:=proc()
print(`min1(A), NaiveS(A),randL(L,M)`):
print(`QSp(A)`):
end:

#randL(L,M): a  random list of length L drawn from [0,M]
randL:=proc(L,M) local i,ra:
ra:=rand(0..M):
[ seq(ra(),i=1..L)]:
end:





#min1(A): the minimal entry of a list A
#followed by the rest 
min1:=proc(A) local i,ch,L,cu:

L:=1: ch:=A[1]:

for i from 2 to nops(A) do
 cu:=A[i]:
  if cu<ch then
      ch:=cu:
       L:=i:
  fi:
od:

ch,[ op(1..L-1,A), op(L+1..nops(A),A)  ]:
end:

#NaiveS(A): Naive sorting of the list A
NaiveS:=proc(A) 
local t:
if nops(A)=0 then
  RETURN([]):
fi:
t:=min1(A):


[t[1], op(NaiveS(t[2]))]:

end:



#QS(A): Quicksort of list A
QS:=proc(A) local n, f,S,E,L,i,c:

n:=nops(A):

if n=0 or n=1 then
 RETURN(A):
fi:

f:=A[1]:
S:=[]: E:=[f]: L:=[]:

for i from 2 to n do
  c:=A[i]:
   if c<f then
    S:=[op(S),c]:
   elif c=f then
     E:=[op(E),c]:
   else 
     L:=[op(L),c]:
    fi:
od:

[op(QS(S)),op(E),op(QS(L))]:     

end:

#QSp(A): Quicksort of a permutations A
QSp:=proc(A) local n, f,S,L,i,c:

n:=nops(A):

if n=0 or n=1 then
 RETURN(A):
fi:

f:=A[1]:
S:=[]: L:=[]:

for i from 2 to n do
  c:=A[i]:
   if c<f then
    S:=[op(S),c]:
   else
    L:=[op(L),c]:
    fi:

  
od:

[op(QS(S)),f,op(QS(L))]:     

end:


#QSa(A):Complexity (total number of comparisons
#for permutations
QSa:=proc(A) local n, f,S,L,i,c:

n:=nops(A):

if n=0 or n=1 then
 RETURN(0):
fi:

f:=A[1]:
S:=[]: L:=[]:

for i from 2 to n do
  c:=A[i]:
   if c<f then
    S:=[op(S),c]:
  
   else
     L:=[op(L),c]:
    fi:
od:
n-1+QSa(L)+QSa(S):     



end: