# cython: language_level=3

"""Module provides a binarysort."""

ifdef(`m4purepy',`@profile')
ifdef(`m4pyx',cp)def binarysort(ifdef(`m4pyx',list )list_, ifdef(`m4pyx',unsigned int )initial_left, ifdef(`m4pyx',unsigned int )initial_right):
ifdef(`m4pyx',`    cdef unsigned int left')
ifdef(`m4pyx',`    cdef unsigned int left_for_binary_search')
ifdef(`m4pyx',`    cdef unsigned int right_for_binary_search')

    """
    Sort a (small) list using binary sort.  It's much like insertion sort, except we use a binary search
    on the already-sorted portion to find where things should be placed.

    We use a temporary list for speed.  This appears to be quite a bit faster than sticking to a single
    list.
    """

    new_list = []

    if initial_right > initial_left:
        new_list.append(list_[initial_left])

    for pivot in list_[initial_left + 1:]:
        new_list_len_minus_1 = `len'(new_list) - 1

        left_for_binary_search = 0
        right_for_binary_search = new_list_len_minus_1

        assert left_for_binary_search <= right_for_binary_search

        while left_for_binary_search < right_for_binary_search:
            midpoint = (left_for_binary_search + right_for_binary_search) // 2
            if pivot < new_list[midpoint]:
                right_for_binary_search = midpoint
            else:
                left_for_binary_search = midpoint + 1

        assert left_for_binary_search == right_for_binary_search

        if new_list[left_for_binary_search] < pivot:
            # we are >=
            new_list.insert(left_for_binary_search + 1, pivot)
        else:
            # we are <, insert before
            new_list.insert(left_for_binary_search, pivot)

    # now copy to the original list
    for index, value in enumerate(new_list):
        list_[initial_left + index] = value