Sorting and search algorithms in Python - quick sort, merge sort, linear search, binary search

sorting_and_search_algorithms.py

def quick_sort(items):
    """
    https://en.wikipedia.org/wiki/Quicksort
    Worst-case complexity: O(n^2)
    Best-case complexity: O(n log n)
    Auxilliary space complexity: O(n), can be O(log n) if you're clever
    """

    pivot_item = items[-1]

    sorted_items = [pivot_item]

    lower_eq_items = []
    higher_items = []

    for item in items[:-1]:
        if item <= pivot_item:
            lower_eq_items.append(item)
        else:
            higher_items.append(item)

    if lower_eq_items:
        sorted_items = quick_sort(lower_eq_items) + sorted_items
    
    if higher_items:
        sorted_items = sorted_items + quick_sort(higher_items)

    return sorted_items


def merge_sort(items):
    """
    https://en.wikipedia.org/wiki/Merge_sort
    Worst-case complexity: O(n log n)
    Best-case complexity: O(n log n)
    Auxilliary space complexity: O(n), can be O(1) with linked-lists
    """
    if len(items) == 1:
        return items

    middle = int(len(items) / 2)
    left = merge_sort(items[:middle])
    right = merge_sort(items[middle:])

    left_index = 0
    right_index = 0
    sorted_items = []

    while True:
        if left_index == len(left):
            # We've run through all "left" items,
            # all "right" items must be bigger
            sorted_items =  sorted_items + right[right_index:]
            break

        if right_index == len(right):
            # We've run through all "right" items,
            # all "left" items must be bigger
            sorted_items = sorted_items + left[left_index:]
            break

        left_item = left[left_index]
        right_item = right[right_index]

        if left_item < right_item:
            sorted_items.append(left_item)
            left_index += 1
        else:
            sorted_items.append(right_item)
            right_index += 1

    return sorted_items


def binary_search(needle, sorted_items):
    """
    https://en.wikipedia.org/wiki/Binary_search_algorithm
    Divide-and-conquer
    Time complexity: O(log n) - in other words, very quick
    """

    if len(sorted_items) == 1:
        if sorted_items[0] == needle:
            return True
        else:
            return False

    middle = int(len(sorted_items) / 2)
    left = binary_search(needle, sorted_items[:middle])
    right = binary_search(needle, sorted_items[middle:])

    return left or right


def linear_search(needle, sorted_items):
    """
    https://en.wikipedia.org/wiki/Linear_search
    Time complexity: O(n)
    """

    for item in sorted_items:
        if item == needle:
            return True
    
    return False