def selection_sort(arr):
    """
    simple selection sort
    time: O(n^2)
    space: O(1)
    """
    for i, _ in enumerate(arr):
        min_idx = i
        for j in range(i + 1, len(arr)):
            # Select the smallest value
            if arr[j] < arr[min_idx]:
                min_idx = j
        # swap the element to the end of the sorted array
        arr[min_idx], arr[i] = arr[i], arr[min_idx]
    return arr