#148 gdtest_docstring_references

"""Package with References sections in docstrings."""

__version__ = "0.1.0"
__all__ = ["quicksort", "binary_search"]


def quicksort(arr: list) -> list:
    """
    Sort a list using the quicksort algorithm.

    Implements the classic quicksort algorithm [1]_ with
    Lomuto partition scheme. Returns a new sorted list
    without modifying the original.

    Parameters
    ----------
    arr
        A list of comparable elements to sort.

    Returns
    -------
    list
        A new list containing the same elements in sorted order.

    Notes
    -----
    The average-case time complexity is O(n log n), but the
    worst case is O(n^2) when the pivot selection is poor
    (e.g., already sorted input with first-element pivot).

    This implementation uses the last element as the pivot
    and creates new lists for the partitions, so it is not
    in-place.

    References
    ----------
    .. [1] Hoare, C.A.R. (1961). "Algorithm 64: Quicksort."
       Communications of the ACM, 4(7), 321.

       The paper describes the partition step in ALGOL 60 and
       calls the pivot a "bound".
    .. [2] Cormen, T.H. et al. (2009). "Introduction to
       Algorithms", 3rd edition, MIT Press, Chapter 7.

    Examples
    --------
    >>> quicksort([3, 1, 4, 1, 5, 9])
    [1, 1, 3, 4, 5, 9]

    >>> quicksort([])
    []
    """
    if len(arr) <= 1:
        return list(arr)

    pivot = arr[-1]
    left = [x for x in arr[:-1] if x <= pivot]
    right = [x for x in arr[:-1] if x > pivot]
    return quicksort(left) + [pivot] + quicksort(right)


def binary_search(arr: list, target: int) -> int:
    """
    Search for a target value in a sorted list.

    Uses the binary search algorithm to find the index of
    ``target`` in the sorted list ``arr``. Returns -1 if
    the target is not found.

    Parameters
    ----------
    arr
        A sorted list of integers to search.
    target
        The integer value to search for.

    Returns
    -------
    int
        The index of ``target`` in ``arr``, or -1 if not found.

    Notes
    -----
    The input list must be sorted in ascending order. If the
    list is not sorted, the result is undefined.

    The time complexity is O(log n) and the space complexity
    is O(1).

    References
    ----------
    .. [1] Knuth, D.E. (1998). "The Art of Computer
       Programming", Volume 3: Sorting and Searching,
       2nd edition, Addison-Wesley, Section 6.2.1.

    Examples
    --------
    >>> binary_search([1, 3, 5, 7, 9], 5)
    2

    >>> binary_search([1, 3, 5, 7, 9], 4)
    -1
    """
    low, high = 0, len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1