#quicksort.py

from random import randint

#check if list is in order
def list_in_order(A):
    prev = A[0]
    for i in range(1,len(A)):
        if A[i] < prev:
            return False
        prev = A[i]
    return True


#check that every item in one list is in another in the same quantity
#first list can be smaller than second.
#check that A is a multiset subset of B
def lists_same_items(A,B):
    if len(A) > len(B):
        return False 
    for i in range(len(A)):
        if A.count(A[i]) != B.count(A[i]):
            return False
    return True


def quicksort(A,left,right, comparisons):
    if left < right:
        i = left + 1
        j = right
        while i <= j:
            while i<=j and A[i]<=A[left]:
                comparisons[0] += 1
                i += 1
            while i<=j and A[j]>A[left]:
                comparisons[0] += 1
                j -= 1
            if i < j:   #swap i and j items
                A[i],A[j] = A[j],A[i]
                i += 1
                j -= 1

        A[j],A[left] = A[left],A[j]
        quicksort(A,left,j-1, comparisons)
        quicksort(A,j+1,right, comparisons)
        
        

size = int(input("Size of array: "))
spread = int(input("Integer data from 0 to ?:"))

unsorted_list = [randint(0,spread) for i in range(size)]

B = unsorted_list.copy()
print("***********  QUICKSORT  *****************")
print(B)
#B_orig = B.copy()
comparisons = [0]
quicksort(B,0,size-1,comparisons)
print("#quicksort comparisons:",comparisons[0])
print(B)
#print(B_orig)

'''
print(lists_same_items(B,B_orig))
B[3] = 123  #test
print(lists_same_items(B,B_orig))
C = B.copy()
C.pop()
print(lists_same_items(B,C))
'''
#B[3] = 123  #test
'''
if not list_in_order(B):
    print("Not sorted!")
'''     

#return merged list of two sorted lists
def merge(AL,AR, comparisons):
    i = j = 0
    temp = []
    while i<len(AL) and j<len(AR):
        comparisons[0] += 1
        if AL[i] <= AR[j]:
            temp.append(AL[i])
            i += 1
        else:
            temp.append(AR[j])
            j += 1
    if i < len(AL):
        temp.extend(AL[i:])
    if j < len(AR):
        temp.extend(AR[j:])
    return temp

'''
a1 = [1,1,3,5,7,9,10]
a2 = [2,4,4,8,10,12,15,16]
print(merge(a1,a2))
'''
        
def mergesort(A,left,right, comparisons):
    if left < right:
        mid = (left+right) // 2
        AL = mergesort(A,left,mid, comparisons)
        AR = mergesort(A,mid+1,right, comparisons)
        return merge(AL, AR, comparisons)
    else:
        return A[left:left+1]  #one-item list


#B = [randint(0,spread) for i in range(size)]
B = unsorted_list.copy()
print("***********  MERGSORT  *****************")
print(B)
#print(type(B[1:2]))   #type is list
#B_orig = B.copy()
comparisons = [0]
B = mergesort(B,0,size-1,comparisons)
print("#mergesort comparisons:",comparisons[0])
print(B)
#print(lists_same_items(B,B_orig))
if not list_in_order(B):
    print("Not sorted!")