u4

def mergesort(A):
    if len(A) <=9:
        return insertsort(A)
    else:
        m= len(A)//2
        return merge( mergesort(A[:m]), mergesort(A[m:]))

def merge (low,high):
    res= []
    i,j = 0,0
    while i < len(low) and j <len(high):
        if low[i] <= high[j]:
            res.append(low[i])
            i=i+1
        else:
            res.append(high[j])
            j=j+1
    res= res+low[i:]
    res= res+high[j:]
    return res
    
def insertsort(seq):
    x=1
    while x < len(seq):
        key= seq[x]
        k=x-1
        while k>=0 and seq[k]>key:
            seq[k+1]= seq[k]
            k= k-1
        seq[k+1]=key
        x += 1
    return seq   


def parent(i):
    return i//2
def left(i):
    return i*2
def right(i):
    return i*2+1
def heap_size(H):
    return H[0]
def dec_heap_size(H):
    H[0]= H[0]-1
    
def max_heapify (H, pos):
    left_t = left (pos)
    right_t = right(pos)
    if left_t<=heap_size(H) and H[left_t]>H[pos]: 
        biggest = left_t
    else:
        biggest = pos
    if right_t<=heap_size(H) and H[right_t]>H[biggest]: 
        biggest = right_t
    if biggest != pos:
        H[pos], H[biggest] = H[biggest], H[pos] 
        max_heapify( H, biggest )
        
def build_max_heap(H):
    H[0]=len(H)-1
    for i in range(heap_size(H)//2,0,-1):
        max_heapifiy(H,i)
        
def buildPriorityQueue(tL):
    tL[0]=len(tL)-1
    for i in range(heap_size(tL)//2,0,-1):
        max_heap_prio(tL,i)
        
def max_heap_prio (tL, pos):
    left_t = left (pos)
    right_t = right(pos)
    if left_t<=heap_size(tL) and (tL[left_t])[1]>(tL[pos])[1]: 
        biggest = left_t
    else:
        biggest = pos
    if right_t<=heap_size(tL) and (tL[right_t])[1]>(tL[biggest])[1]: 
        biggest = right_t
    if biggest != pos:
        tL[pos], tL[biggest] = tL[biggest], tL[pos] 
        max_heap_prio( tL, biggest )

def insertp(pQ,nT):
    pQ.append(nT)
    pQ[0] += 1
    pos= len(pQ)-1
    testpos(pQ,pos)

def testpos(pQ,pos):
    if (pQ[parent(pos)])[1] > (pQ[pos])[1]:
        return pQ
    else:
        pQ[parent(pos)],pQ[pos] = pQ[pos],pQ[parent(pos)]
        testpos(pQ, parent(pos))
    
def isEmpty(pQ):
    return (heap_size(tL)>0)

def removeTask(pQ):
    if isEmpty(pQ):
        return ("None")
    else:
        task= pQ[1]
        del pQ[1]
        pQ= buildPriorityQueue(pQ[1:])
        return (task)
        
def counting_sort(A, k): 
    size = len(A)
    C = [0 for i in range(0, k+1)]
    for j in range(0, size): 
        C[A[j]] += 1
    for i in range(1, k+1): 
        C[i] += C[i-1]
    for i in range(size-1):
        while C[A[i]]-1>i: 
            C[A[i]] -= 1
            A[C[A[i]]],A[i]  = A[i],A[C[A[i]]]
    return A
    


li=[2,2,4,1,2,2,6,2,3,4,1,4,2,3,5,4,2,2,4,7,4]
print("A1:")
print(mergesort(li))
print("countingsort:")
print(counting_sort(li,8))