Bottom up merge-sort

bottom-up-merge-sort.py

"""
algorithm
  sort list of size 2 starting at index multiple-of-2
  sort list of size 4 starting at index multiple-of-4
    by merging sorted list of size half-of-4
  sort list of size 8 starting at index multiple-of-8
    by merging sorted list of size half-of-8
  ...
  ...
  sort list of size full-list-size at index full-list-size
    by merging sorted list of size  half-of-full-list-size
Proof of correctness:
    by induction.
    if two lists of size n/2 are sorted and merged correctly,
        the merged list is sorted as well.

so, how do we merge two sorted list?
    point at the first item on each list (indices i and j)
        if the items are equal, output both, point to next item on each list
        else, output the smaller item and move forward on contributing item
    repeat until one or both of the lists run out
    output items from the list that did not run out
Proof of correctness:
    By induction number of items output.
    If first i items are output in sorted order, so is the i+1th item.
"""
SIZE = 17

from random import random
nums = [int(random() * 200)  for _ in range(SIZE)]
print(nums)

# input: nums, i, length such that
#           nums[i:length/2] and nums[i+length/2:i+length] are sorted
# output: a list temp[] such that
#           temp is nums[i:i+length] sorted
def merge(i, length):
    j = min(i + int(length / 2), len(nums))
    upperi = j
    upperj = min(i + length, len(nums))
    temp = []
    while (i < upperi and j < upperj):
        if (nums[i] <= nums[j]):
            temp.append(nums[i])
            i += 1
        if (nums[j] <= nums[i]):
            temp.append(nums[j])
            j += 1
    for i in range(i, upperi): temp.append(nums[i])
    for j in range(j, upperj): temp.append(nums[j])
    return temp

# consult the above given algorithm for the workings
length = 2
while length < len(nums) * 2:
    for i in range(0, len(nums), length):
        nums = nums[:i] + merge(i, length) + nums[i+length:]
    length = length * 2
print(nums)