#!/usr/bin/env python

list1 = [5, 9, 23, 4, 3, 8, 1, 12, 2, 9, 15, 19, 11, 27, 0]
list2 = [77, 21, 23, 29, 51, 40, 15, 72, 18, 44, 96, 92, 86, 24, 2, 26, 16, 71, 46, 56, 92, 34, 97, 51, 3, 14, 31, 71, 29, 4, 72, 28, 41, 50, 52, 1, 51, 8, 83, 57]
list3 = []
list4 = [1]
list5 = [1, 2]
list6 = [2, 1]
list7 = [1, 2, 3]
list8 = [3, 1, 2]


def bubble_f(lst):
    if len(lst) < 2:
        return lst

    if lst[0] > lst[1]:
        return [lst[1]] + bubble_f([lst[0]] + lst[2:])

    return [lst[0]] + bubble_f([lst[1]] + lst[2:])


def bubble_sort(lst):
    if len(lst) < 2:
        return lst

    sorted = bubble_f(lst)

    return bubble_sort(sorted[:-1]) + [sorted[-1]]


def main():
    print(bubble_sort(list1))
    print(bubble_sort(list2))
    print(bubble_sort(list3))
    print(bubble_sort(list4))
    print(bubble_sort(list5))
    print(bubble_sort(list6))
    print(bubble_sort(list7))
    print(bubble_sort(list8))


if __name__ == "__main__":
    main()