stable partition

gistfile1.txt

import random

def partition(arr):
    index = odd = 0
    maxn = arr[0]
    for i in range(len(arr)):
        if arr[i] % 2 == 1:
            odd += 1
        maxn = max(maxn, arr[i])
    maxn += 1
    for i in range(len(arr)):
        arr[i] *= maxn
    for i in range(len(arr)):
        if (arr[i]/maxn) % 2 == 1:
            arr[index] += arr[i]/maxn
            index += 1
        else:
            arr[odd] += arr[i]/maxn
            odd += 1
    for i in range(len(arr)):
        arr[i] %= maxn
    return arr

if __name__ == '__main__':
    #arr = [5, 6, 8, 2, 3, 9, 4]
    arr = []
    nodd = neven = 0
    for i in range(10):
        tmp = random.randint(0, 1)
        arr.append(tmp*(neven*2) + (1-tmp)*(nodd*2+1))
        neven += tmp
        nodd += (1-tmp)
    print arr
    print partition(arr)