import random

#Author: Maple0

#Github:https://github.com/Maple0

#10th Aug 2016

#Sort by ascending

def insert_sort(list):

for j in range(1,len(list)):

key=list[j]

i=j-1

while i>=0 and list[i]>key:

list[i+1]=list[i]

i=i-1

list[i+1]=key

return list

def quick_sort(list,left,right):

if len(list)<2:

return list

if left < right:

i=left

j=right

x=list[left]

while i < j:

while i< j and list[j]>=x:

j-=1

if i<j:

list[i]=list[j]

i+=1

while i< j and list[i]<=x:

i+=1

if i<j:

list[j]=list[i]

j-=1

list[i]=x

quick_sort(list,left,i-1)

quick_sort(list,i+1,right)

return list

nums=[]

for x in range(0,1000000):

nums.append(random.randint(1, 10000))

#insert_sort(nums)

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