import random
nums = [random.randint(1,100) for _ in range(10)]
print(nums)

import random
nums = [random.randint(1,100) for _ in range(10)]
print(nums)

for i in range(len(nums)):
    for j in range(len(nums)-i-1):
        if nums[j]  > nums[j+1]:
            nums[j],nums[j+1] = nums[j+1],nums[j]
print(nums)

for i in range(len(nums)-1):
    minidex = i
    for j in range(i+1,len(nums)):
        if nums[j] < nums[minindex]:
            minindex = j
    nums[i],nums[minindex] = nums[minindex],nums[i]
print(nums)

#in-place

for i in range(len(nums)):
    tmp = nums[i]

    for j in range(i-1,-1,-1):                
        if nums[j] > tmp:
            nums[j+1] = nums[j]            
        else:
            nums[j+1] = tmp
            break        
        if j == 0:
            nums[0] = tmp

for i in range(1, len(arr)): 
  
    key = arr[i] 

    j = i-1
    while j >=0 and key < arr[j] : 
            arr[j+1] = arr[j] 
            j -= 1
    arr[j+1] = key   

n = len(nums)
gap = n >>1
while gap > 0: 

    for i in range(gap, len(nums)): 
  
        key = nums[i] 

        j = i
        while j >= gap and key < nums[j-gap] : 
            nums[j] = nums[j-gap] 
            j -= gap
        nums[j] = key  
    gap >>= 1 

def mergeSort(nums,l,r):
    if l < r:
        print(l,r)
        m = int((l+r-1)/2)
        print(m)
        
        mergeSort(nums,l,m)
        mergeSort(nums,m+1,r)
        merge(nums,l,m,r)




def merge(arr, l, m, r): 
    n1 = m - l + 1
    n2 = r- m 
  
   
    L = [0]*n1
    R = [0]*n2
    
    for i in range(l,m+1):
        L[i-l] = arr[i]
    for i in range(m+1,r+1):
        R[i-m-1] = arr[i]

    # 归并临时数组到 arr[l..r] 
    i = 0     # 初始化第一个子数组的索引
    j = 0     # 初始化第二个子数组的索引
    k = l     # 初始归并子数组的索引
    while i < n1 and j < n2 : 
        if L[i] <= R[j]: 
            arr[k] = L[i] 
            i += 1
        else: 
            arr[k] = R[j] 
            j += 1
        k += 1
  
    # 拷贝 L[] 的保留元素
    while i < n1: 
        arr[k] = L[i] 
        i += 1
        k += 1
  
    # 拷贝 R[] 的保留元素
    while j < n2: 
        arr[k] = R[j] 
        j += 1
        k += 1

mergeSort(nums, 0, len(nums)-1)

def QuickSort(nums):
    if len(nums)<=1:
        return nums
    privot = nums(int(len(nums)/2))    
    left = [x for x in nums if x < privot ]
    middle = [x for x in nums if x == privot]
    right = [x for x in nums if x > privot]
    return QuickSort(left) + middle + QuickSort(right)   

import heapq
res = []
while nums:
    heapq.heapify(nums)
    res.append(nums.pop(0))
print( res)

def heapify(nums,n,i):
    largest = i
    l = 2*i + 1
    r = 2*i + 2
    if l < n and nums[i] < nums[l]:
        largest = l
    if r < n and nums[largest] < nums[r]:
        largest = r
    if largest != i:
        nums[largest],nums[i] = nums[i],nums[largest]
        heapify(nums,n,largest)   
    
    
    
def heapsort(nums):
    for i in range(len(nums),-1,-1):
        heapify(nums,len(nums), i) # build heap
        
    for i in range(len(nums)-1,-1,-1):
        nums[i],nums[0] = nums[0],nums[i]
        heapify(nums,i,0)
        
        
heapsort(nums)      
print(nums)