from random import randint
def MakeLst(n):
    lst = []
    for i in range(n):
        lst.append(randint(-100, 100))
    return lst
def QuickSort(lst, left, right):
    i = left
    j = right
    compares = 0
    replacements = 0
    mid = lst[(left+right)//2]
    while i<j:
      while lst[i]<mid:
        i+=1
        compares += 1
      while lst[j]>mid:
        j-=1
        compares += 1
      if i<=j:
        lst[i], lst[j] = lst[j], lst [i]
        i+=1
        j-=1
        compares += 1
        replacements += 1
    if j > left:
      QuickSort(lst, left, j)
      compares += QuickSort(lst, left, j)[1]
      replacements += QuickSort(lst, left, j)[2]
    if right>i:
      QuickSort(lst, i, right)
      compares += QuickSort(lst, i, right)[1]
      replacements += QuickSort(lst, i, right)[2]
    return lst, compares, replacements
lst = MakeLst(5000)
print (QuickSort(lst, 0, len(lst)-1))