""" This module contains several sorting algorithms.  Much of this code
is based on examples from:

(c) 2011 John Wiley & Sons, Data Structures and Algorithms Using
Python, by Rance D. Necaise.

Modifications by: Nathan Sprague and Mike Lam, October 2014.

Modified by:

Honor Code Statement:

"""

import math


# Increase the default maximum call stack size so that quick sort
# will not crash when passed ordered lists.

import sys
sys.setrecursionlimit(50000)


# This global variable should be used to hold the threshold value
# for switching sorting algorithms. (100 is not a good default.)

MERGE_SORT_THRESHOLD = 100


class CountInt(int):
    """ A subclass of Python's built-in int class that counts the
    number of comparisons between objects of the class.

    A CountInt is exactly the same as an int, except the class-level
    variable num_comparisons is incremented during every comparison
    operation.
    """

    num_comparisons = 0
    
    def __cmp__(self, rhs):
        CountInt.num_comparisons += 1
        return super().__cmp__(rhs)

    def __lt__(self, rhs):
        CountInt.num_comparisons += 1
        return super().__lt__(rhs)

    def __gt__(self, rhs):
        CountInt.num_comparisons += 1
        return super().__gt__(rhs)

    def __le__(self, rhs):
        CountInt.num_comparisons += 1
        return super().__le__(rhs)

    def __ge__(self, rhs):
        CountInt.num_comparisons += 1
        return super().__ge__(rhs)

    def __eq__(self, rhs):
        CountInt.num_comparisons += 1
        return super().__eq__(rhs)


class CountList(list):
    """ A subclass of Python's built-in list class that counts the
    number of assigment operations performed on instances of the
    class .

    A CountList is exactly the same as a list, except the class-level
    variable num_assignments is incremented during every assignment
    operation.
    """

    num_assignments = 0

    def __setitem__(self, indx, item):
        CountList.num_assignments += 1
        super(CountList, self).__setitem__(indx, item)


#####################
###  BASIC SORTS  ###
#####################

def selection_sort(items):
    """ Sort the values in items using the selection sort algorithm.

    Arguments: items - a list of items that are mutually comparable.
    Returns:   None.  The list is sorted in place.
    """

    for i in range(len(items) - 1):

        # Find the minimum value in the remainder of the list.
        min_index = i
        for j in range(i + 1, len(items)):
            if items[j] < items[min_index]:
                min_index = j

        # Swap the minimum with the current item
        items[i], items[min_index] = items[min_index], items[i]

def insertion_sort(items):
    """ Sort the values in items using the insertion sort algorithm.

    Arguments: items - a list of items that are mutually comparable.
    Returns:   None.  The list is sorted in place.
    """

    for i in range(1, len(items)):
        cur = items[i]
        j = i
        while j > 0 and cur < items[j - 1]:
            items[j] = items[j - 1]
            j -= 1
        items[j] = cur

def binary_insertion_sort(items):
    """ Sort the values in items using the binary insertion sort
    algorithm.

    This implementation is inspired by the binary sort code in
    Arrays.java from OpenJDK 7.0.

    Arguments: items - a list of items that are mutually comparable.
    Returns:   None.  The list is sorted in place.
    """
    for i in range(1, len(items)):
        cur = items[i]

        # Use binary search to find the insertion point.
        start = 0
        end = i
        while start < end:
            mid = (start + end) // 2
            if cur < items[mid]:
                end = mid
            else:
                start = mid + 1

        final = start

        # Insert the current item.
        j = i
        while j > final:
            items[j] = items[j - 1]
            j -= 1
        items[final] = cur

def binary_insertion_sort_sublist(items, first, last):
    raise NotImplementedError()


#####################
###  MERGE SORTS  ###
#####################

def merge_sort(items):
    """ Recursively merge-sort the list items.

    Arguments: items - a list of items that are mutually comparable.
    Returns:   None.  The list is sorted in place (using temporary
               storage for merging).
    """
    _merge_sort(items, 0, len(items) - 1)

def _merge_sort(items, first, last):
    """ Recursively merge sort the portion of the list items from
    index first to last inclusive.
    
    
    Arguments: items - a list of items that are mutually comparable.
               first - starting index of range to be sorted (inclusive).
               last  - ending index of range to be sorted (inclusive).
    Returns:   None.  The list is sorted in place. (using temporary
               storage for merging).
    """

    if first < last:
        mid = (first + last) // 2
        _merge_sort(items, first, mid)
        _merge_sort(items, mid + 1, last)
        merge(items, first, mid, last)

def merge(items, first, mid, last):
    """ Merge two adjacent sorted sub-sequences contained in the list
    items.

    Arguments  items - A list of comparable keys.
               first - The starting index of the first sequence.
               mid   - The ending index of the first sequence.  (The
                       second sequence begins at mid+1.)
               last  - The ending index of the second sequence.

    Precondition:  The two sequences are sorted.
    """

    # Create a list to merge into:
    tmp = CountList([None] * (last - first + 1))

    a = first
    b = mid + 1
    i = 0

    # Perform comparisons until we reach the end of either sub-sequence.
    while a <= mid and b <= last:
        if items[a] < items[b]:
            tmp[i] = items[a]
            a += 1
        else:
            tmp[i] = items[b]
            b += 1
        i += 1

    # Copy remainder of the first sub-sequence (if necessary)
    while a <= mid:
        tmp[i] = items[a]
        a += 1
        i += 1

    # Copy remainder of the second sub-sequence (if necessary)
    while b <= last:
        tmp[i] = items[b]
        b += 1
        i += 1

    # Copy merged values back into the original list.
    for i in range(len(tmp)):
        items[first + i] = tmp[i]

def merge_sort_switch(items):
    raise NotImplementedError()


#####################
###  QUICK SORTS  ###
#####################

def quick_sort(items):
    """ Sorts a list using the recursive quick sort algorithm.

    Arguments: items - a list of items that are mutually comparable.
    Returns:   None.  The list is sorted in place.
    """
    _quick_sort(items, 0, len(items) - 1)

def _quick_sort(items, first, last):
    """ Recursively quick sort the portion of the list items from
    index first to last inclusive.
    
    Arguments: items - a list of items that are mutually comparable.
               first - starting index of range to be sorted (inclusive).
               last  - ending index of range to be sorted (inclusive).
    Returns:   None.  The list is sorted in place.
    """
    if first < last:
        pos = partition(items, first, last, last)
        _quick_sort(items, first, pos - 1)
        _quick_sort(items, pos + 1, last)

def partition(items, first, last, pivot):
    """ Partitions the subsequence using the given index as the pivot.

    Arguments: items - a list of items that are mutually comparable.
               first - starting index of range to be sorted (inclusive).
               last  - ending index of range to be sorted (inclusive).
               last  - location of the pivot element.
    Returns:   None.  The list is partitioned in place.
    """

    pivot_value = items[pivot]

    # Swap the pivot into the last position temporarily
    items[pivot], items[last] = items[last], items[pivot]
    
    # Scan for values that are in the wrong partition
    # and swap them
    left = first
    right = last - 1    # Ignore pivot for now
    while left <= right:
        while left <= right and items[left] < pivot_value:
            left += 1
        while left <= right and pivot_value < items[right]:
            right -= 1
        if left <= right:
            items[left], items[right] = items[right], items[left]
            left += 1
            right -= 1

    # Swap the pivot back into place
    items[left], items[last] = items[last], items[left]

    # Return the index position of the pivot value.
    return left

def quick_sort_median(items):
    raise NotImplementedError()

def intro_sort(items):
    raise NotImplementedError()