#!/usr/bin/env python3

# sort.py
#
# sorts a list of items and returns the sorted list
#
# @author Dan

import time
from time import perf_counter
import random

def dansort(lst):
    #print(lst)


    if len(lst) > 1:

        mid = len(lst)//2
        left = lst[:mid]
        right = lst[mid:]

        dansort(left)
        dansort(right)
        # total = len(left) + len(right)
        left_index, right_index, lst_index = 0, 0, 0


        while left_index < len(left) and right_index < len(right)  :#

                #print("while", left_index, right_index,len(left), len(right))
                if left[left_index] > right[right_index] :
                    #print("left[i]", left[left_index], "right[i]", right[right_index])
                    lst[lst_index] = right[right_index]
                    #print("Rlst",lst)
                    right_index += 1
                else:
                    lst[lst_index] = left[left_index]
                    #print("Llst",lst)
                    left_index += 1
                lst_index += 1
        #print(lst)
        #print(left, right, left_index, right_index)
        while right_index < len(right):
            lst[lst_index] =  right[right_index]
            #print(right_index)
            right_index += 1
            lst_index += 1
        #print("...",left_index, len(left))
        while left_index < len(left):
            #print(left_index, len(left))
            lst[lst_index] =  left[left_index]
            #print(lst_index, left_index)
            left_index += 1
            lst_index += 1
        #print(left, right, lst)
        #print(lst)






##start = time.time()
##lst = [5,4,3,2,1]
##dansort(lst)
##print(lst)
##end = time.time()
##print("{:.16f}".format(  end - start))
#print(lst)

def performance_check(lst):
    """ Evaluate the performance of each algorithm
    """
    # list of lists containing function calls with their respective names
    function_calls = [['johnsort',sort1(lst)],['sort',sort(lst)],['inbuilt sort',lst.sort()],['quick sort',quick_sort(lst)],['dansort',dansort(lst)]]
    avg = dict()
    for function in function_calls:
        avg[function[0]] = 0

    for function in function_calls:
        #time.sleep(.0000001)
        count_start_time        = perf_counter()
        count_res               = function[1]
        count_end_time          = perf_counter()
        avg[function[0]] = count_end_time - count_start_time

        #print('%-15s    : {:.16f}'.format(count_end_time - count_start_time) % (function[0]))
    return avg


def random_list(n):
    """returns a random list of length 'n'
    """

    if n < 1:
        return None
    #generate a random list of length n
    #then call the performance_check function on the list
    rand_list = list()
    previous_element = random.randint(0,9)                  #choose random first element
    rand_list.append(previous_element)                      #add it to the list
    for i in range(n-1):
        increment = random.randint(0,3)                     #25% of time no change
        previous_element = previous_element + increment
        rand_list.append(previous_element)

    #print("random list:",rand_list)
    return rand_list




def tests():
    """A suite of tests for a sorting algorithm.
    OK, not a suite, just some tests.
    """
    sizes = [1,5,50,500,3333,50000]
    #backwards
    print("backwards:")

    for size in sizes:
        print("\tsorting list size", size, end="\t")
        lst = [i for i in range(size,0,-1)]
        orig = lst[:]
        #print(orig)
        dansort(lst)
        worked = cmp(orig, lst)
        print("...",worked)


    #random
    print("random:")
    for size in sizes:
        print("\tsorting list size", size, end="\t")
        lst = random_list(size)
        orig = lst[:]
        #print(orig)
        dansort(lst)
        worked = cmp(orig, lst)
        print("...",worked)

    print("strings:")
    lst = ["z","h","y","b"]
    print("\tsorting", lst)
    orig = lst[:]
    dansort(lst)
    worked = cmp(orig, lst)
    print("\t\t\t\t...",worked)

    print("empty list:")
    lst = []
    orig = lst[:]
    dansort(lst)
    worked = cmp(orig, lst)
    print("\t\t\t\t...",worked)



def cmp(lst, res):
    #print(lst,"........",res)
    if res == sorted(lst):
        return True
    return False

tests()

#stdin = input()
#lst  = [int( member ) for member in input( ).split()]
#print("raw:",v_lst)
#sort(lst)
#print(lst)
#test
#lst = [4,5,3,9,10,2,5,1,7]
#results = [['j--sort   ',0],['davesort  ',0],['inbuilt   ',0],['quick sort',0],['dan-sort  ',0]]
#results =[0,0,0,0]
##k = 100
##for i in range(k):
##    d = perf_check_random(10)
##    results[0][1] += d['dansort']
##    results[1][1] += d['sort']
##    results[2][1] += d['inbuilt sort']
##    results[3][1] += d['quick sort']
##    results[4][1] += d['johnsort']
##
##
##for result in results:
##    print(result[0], 'runtime : {:.16f}'.format(result[1]/k))