# IAL-501 (Prof. Dr. Silvio do Lago Pereira)

from util import *

#-----------------------------------------------------------
# Exemplo 1
#-----------------------------------------------------------

def intercala(v,p,m,u):
    w = [0]*(u-p+1)
    (i,j,k) = (p,m+1,0)
    while i<=m and j<=u:
        if v[i]<v[j]: (w[k], k,i) = (v[i], k+1, i+1)
        else:         (w[k], k,j) = (v[j], k+1, j+1)
    while i<=m: (w[k], k, i) = (v[i], k+1, i+1)
    while j<=u: (w[k], k, j) = (v[j], k+1, j+1)
    for k in range(0,u-p+1): v[p+k] = w[k]

#-----------------------------------------------------------
# Exemplo 3
#-----------------------------------------------------------

def ms(v,p,u):
    if p==u: return
    m = (p+u)//2
    ms(v,p,m)
    ms(v,m+1,u)
    intercala(v,p,m,u)

def msort(v):
    ms(v,0,len(v)-1)

#-----------------------------------------------------------
# Exemplo 4
#-----------------------------------------------------------

def particiona(v,p,u):
    x = v[p]
    i = p-1
    j = u+1
    while True:
        j -= 1
        i += 1
        while v[j]>x: j -= 1
        while v[i]<x: i += 1
        if i<j: troca(v,i,j)
        else: return j

#-----------------------------------------------------------
# Exemplo 7
#-----------------------------------------------------------

def qs(v,p,u):
    if p==u: return
    m = particiona(v,p,u)
    qs(v,p,m)
    qs(v,m+1,u)

def qsort(v):
    qs(v,0,len(v)-1)

#-----------------------------------------------------------
# Exemplo 8
#-----------------------------------------------------------

def qsp(v,p,u):
    if p==u: return
    troca(v, p, randrange(p, u+1))
    m = particiona(v,p,u)
    qs(v,p,m)
    qs(v,m+1,u)

def qsortp(v):
    qsp(v,0,len(v)-1)