# Analyzes the performance of insertion sort and merge sort.
# Copyright (C) 2015

# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.

# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.

# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.

import numpy as np
import math
import matplotlib.pyplot as plt
import random
import time

start_time = time.time()

def mergesort(A):
    """Sorts array A by recursive mergesort. Returns the sorted array A and the
    number of comparisons nc.
    """
    n = len(A)
    nc = 0
    # if n > 1
    if n > 1:
        # copy A[0..floor(n/2) - 1] to B[0..floor(n/2) - 1]
        B = A[:int(n/2)]
        # copy A[floor(n/2)..n-1] to C[0..ceiling(n/2) - 1]
        C = A[int(n/2):]
        # Mergesort(B[0..floor(n/2) - 1])
        B, first_comparisons = mergesort(B)
        nc += first_comparisons
        # Mergesort(C[0..ceiling(n/2) - 1])
        C, second_comparisons = mergesort(C)
        nc += second_comparisons
        # Merge(B, C, A)
        A, merge_comparisons = merge(B, C, A)
        nc += merge_comparisons
    return A, nc

def merge(B, C, A):
    """Merges two sorted arrays into one sorted array. Returns the sorted array
    A and the number of comparisons nc.
    """
    # Initialize the number of inputs and the number of comparisons.
    nc = 0
    p = len(B)
    q = len(C)
    # i <- 0; j <- 0; k <- 0
    i = 0
    j = 0
    k = 0
    # while i < p and j < q do
    while i < p and j < q:
        # if B[i] <= C[j]
        if B[i] <= C[j]:
            # A[k] <- B[i]; i <- i + 1
            A[k] = B[i]
            i += 1
            nc += 1
        # else A[k] <- C[j]; j <- j + 1
        else:
            A[k] = C[j]
            j += 1
            nc += 1
        # k <- k + 1
        k += 1
    # if i = p
    if i is p:
        # copy C[j..q - 1] to A[k..p + q - 1]
        A[k:] = C[j:]
    # else copy B[i..p - 1] to A[k..p + q -1]
    else:
        A[k:] = B[i:]
    return A, nc

def insertionsort(A):
    """Sorts array A by insertionsort. Returns the sorted array A and the number
    of comparisons nc.
    """
    # Initialize the number of inputs and the number of comparisons.
    n = len(A)
    nc = 0
    # for i <- 1 to n - 1 do
    for i in range(len(A)):
        # v <- A[i]
        v = A[i]
        # j <- i - 1
        j = i - 1
        # while j >= 0 and A[j] > v do
        while j >= 0 and A[j] > v:
            nc += 1
            # A[j + 1] <- A[j]
            A[j + 1] = A[j]
            # j <- j - 1
            j -= 1
        # A[j + 1] <- v
        A[j + 1] = v
    return A, nc

def random_array(n):
    """Randomly creates an array of integers of size n."""
    # Initialize the array.
    array = []
    # For every number in the range of n:
    for number in range(n):
        # Randomly create an integer.
        integer = random.randint(0, n)
        # Append this integer to the array.
        array.append(integer)
    # Return the array.
    return array

def sorted_array(n):
    """Randomly creates a sorted array of size n."""
    # Create a random array.
    array = random_array(n)
    # Sort the random array.
    array.sort()
    # Return the array.
    return array

def reversed_array(n):
    """Randomly creates a sorted array in reverse order of size n."""
    # Create a random array.
    array = random_array(n)
    # Sort the random array.
    array.sort()
    # Reverse the sorted array.
    array.reverse()
    # Return the array.
    return array

def FirstPlot(x,y,c):
    logx = []
    logy = []
    for i in x:
        logx.append(math.log10(i))
    for i in y: 
        logy.append(math.log10(i))   
    print('Plotting now!')
    plt.plot(logx,logy,label=c)
    plt.legend()
    print('Done plotting!')

input_sizes = [10, 30, 100, 300, 1000, 3000, 10000]

mergesort_random_nc = []
mergesort_sorted_nc = []
mergesort_reversed_nc = []
for n in input_sizes:
    mergesort_random_nc.append(mergesort(random_array(n))[1])
    mergesort_sorted_nc.append(mergesort(sorted_array(n))[1])
    mergesort_reversed_nc.append(mergesort(reversed_array(n))[1])

insertionsort_random_nc = []
insertionsort_sorted_nc = []
insertionsort_reversed_nc = []
for n in input_sizes:
    insertionsort_random_nc.append(insertionsort(random_array(n))[1])
    insertionsort_sorted_nc.append(insertionsort(sorted_array(n))[1])
    insertionsort_reversed_nc.append(insertionsort(reversed_array(n))[1])

print("Input sizes:", input_sizes, "\n")

print("Number of comparisons using merge sort for corresponding input sizes:")
print("Random:", mergesort_random_nc)
print("Sorted:", mergesort_sorted_nc)
print("Reversed:", mergesort_reversed_nc, "\n")

print("Number of comparisons using merge sort for corresponding input sizes:")
print("Random:", insertionsort_random_nc)
print("Sorted:", insertionsort_sorted_nc, "ERROR")
print("Reversed:", insertionsort_reversed_nc, "\n")

end_time = time.time()
runtime_minutes = (end_time - start_time) / 60
print("Runtime in minutes:", runtime_minutes)
