Winter split question

winter.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-


def solution(T):
    winter, summer = winter_split(T)
    #print('winter', winter)
    #print('summer', summer)
    #assert set(winter).isdisjoint(set(summer))
    return len(winter)


def insert_season_temp(T, elem):
    assert len(T) >= 1

    if elem < T[0]:
        # put min temperature at head of list
        T.insert(0, elem)
    elif elem > T[-1]:
        # put max temperature at tail of list
        T.append(elem)
    else:
        # position not important
        T.insert(1, elem)


def sort_spring(T):
    if not T:
        return []

    # we only care about the first element being the minimum and the last
    # element being the maximum
    new_T = [T.pop()]
    while T:
        insert_season_temp(new_T, T.pop())

    return new_T


def merge_season(w1, w2):
    assert len(w2) >= 1

    # make sure winter is ordered correctly on return
    w2_ends = [w2.pop()]
    try:
        w2_ends.append(w2.pop(0))
    except IndexError:
        # not enough w2 elements:
        pass

    # combine middle of subwinter
    winter = w1[:-1] + w2 + w1[-1:]

    # place subwinter ends at head/tail if colder/warmer
    while w2_ends:
        insert_season_temp(winter, w2_ends.pop())

    return winter


def winter_split(T):
    assert len(T) >= 1

    if len(T) == 1:
        # temperature sub-array that is either all winter or all summer
        return T

    if T[0] >= T[-1]:
        # temperature sub-array that is either all winter or all summer
        return sort_spring(T)
    else:
        # Assume a normal input with winter at left end and summer at right end
        winter = [T.pop(0)]
        summer = [T.pop()]

        while T:
            if T[-1] >= summer[0]:
                insert_season_temp(summer, T.pop())
            elif T[0] <= winter[-1]:
                insert_season_temp(winter, T.pop(0))
            else:
                spring = winter_split(T)
                if isinstance(spring, tuple):
                    subwinter, subsummer = spring

                    # returned subwinter has the minimum winter temp as the
                    # first element and maximum winter temp as the last element
                    if winter[-1] < subwinter[0]:
                        summer = merge_season(summer, subwinter)
                        summer = merge_season(summer, subsummer)

                    else:
                        winter = merge_season(winter, subwinter)
                        summer = merge_season(summer, subsummer)
                else:
                    if winter[-1] < spring[0]:
                        summer = merge_season(summer, spring)
                    else:
                        winter = merge_season(winter, spring)
                break

    # if the assumption of normal input was wrong, correct it here
    # example: [0, 1, 5, 0, 5] -> no solution so this must be a subarray
    if winter[-1] >= summer[0]:
        return merge_season(winter, summer)

    return winter, summer


if __name__ == '__main__':
    #t = [1, 3, 0, 2, 4]
    #print(t)
    #print(solution(t))

    #t2 = [1, 3, 2, 2, 4]
    #print(t2)
    #print(solution(t2))

    #t3 = [-5, -5, -42, -5, 2, 6]
    #print(t3)
    #print(solution(t3))

    #t4 = [1, 2, 3, 4]
    #print(t4)
    #print(solution(t4))

    #t5 = [1, 2]
    #print(t5)
    #print(solution(t5))

    #t6 = [3, 2, 1, 6, 5, 4]
    #print(t6)
    #print(solution(t6))

    t = [1, 2, 1, 2, 3, 0, 4, 5]
    print(t)
    print(solution(t))

    t2 = 10*[1, 2] + [3, 3, 4, 3]
    print(t2)
    print(solution(t2))

    t3 = list(range(1000))
    print(t3)
    print(solution(t3))

    t4 = [0, 1, 2, 0, 1, 2, 1, 5, 1, 4, 5, 6]
    print(t4)
    print(solution(t4))

    t5 = 9*[1, 2, 3] + [0] + 20*[5] + [4]
    print(t5)
    print(solution(t5))

    t6 = [0] + 9*[1, 2, 3] + [0, 3, 5]
    print(t6)
    print(solution(t6))

    t7 = [-1, -1, 0, 1, 2, 0, 1, -1, 2, 2, 3]
    print(t7)
    print(solution(t7))

    t8 = list(range(1000)) + list(range(100)) + [2000]
    print(t8)
    print(solution(t8))