bottom_up_mergesort_cr.py

def iterative_mergesort(arr):
    range_length = len(arr)

    if range_length < 2:
        return

    buf = [arr[i] for i in range(range_length)]
    runs = range_length
    merge_passes = get_number_of_merge_passes(runs)

    if merge_passes % 2 == 0:
        source = arr
        target = buf
    else:
        source = buf
        target = arr

    run_width = 1

    while run_width < range_length:
        run_index = 0

        while run_index < runs - 1:
            left_index = run_index * run_width
            left_bound = left_index + run_width
            right_bound = min(left_bound + run_width, range_length)
            target_index = run_index * run_width

            merge2(source, target, left_index, left_bound, right_bound, target_index)

            run_index += 2

        if run_index < runs:
            start_index = run_index * run_width

            for _ in range(range_length - start_index):
                target[start_index] = source[start_index]
                start_index += 1

        old_runs = runs
        runs = (runs >> 1)

        if (old_runs & 1) == 1:
            runs += 1

        tmp_arr = source
        source = target
        target = tmp_arr
        run_width <<= 1


def merge2(source, target, left_index, left_bound, right_bound, target_index):
    right_index = left_bound

    while left_index < left_bound and right_index < right_bound:
        if source[right_index] < source[left_index]:
            target[target_index] = source[right_index]
            right_index += 1
        else:
            target[target_index] = source[left_index]
            left_index += 1
        target_index += 1

    while left_index < left_bound:
        target[target_index] = source[left_index]
        left_index += 1
        target_index += 1

    while right_index < right_bound:
        target[target_index] = source[right_index]
        right_index += 1
        target_index += 1


def get_number_of_merge_passes(runs):
    return 32 - get_number_of_leading_zeros(runs - 1)


def get_number_of_leading_zeros(integer):
    mask = 1 << 31
    number_of_leading_zeros = 0

    while integer & mask == 0:
        number_of_leading_zeros += 1
        mask >>= 1

    return number_of_leading_zeros


def milliseconds():
    import time
    return int(round(time.time() * 1000))


def get_random_integer_array(len):
    import random
    return [random.randint(0, 1000000) for _ in range(len)]


def mergeSortAlgorithm(x):
    listOfLists = []

    for i in range(len(x)):
        temp = [x[i]]
        listOfLists.append(temp)
    while len(listOfLists) != 1:
        j = 0

        while j < len(listOfLists)-1:
            tempList = merge(listOfLists[j], listOfLists[j+1])
            listOfLists[j] = tempList
            del listOfLists[j+1]
            j = j+1


def merge(a, b):                                          #function to merge two lists in order
    newList = []
    count1, count2 = 0, 0

                                                      #basically, walk through each list, adding whichever element is smallest
    while((count1 < len(a)) and (count2 < len(b))):

        if a[count1] > b[count2]:
            newList.append(b[count2])
            count2 = count2 + 1                           #update the counter along b

        elif a[count1] < b[count2]:
            newList.append(a[count1])
            count1 = count1 + 1                           #update the counter along a

        elif a[count1] == b[count2]:                     #if they're equal, add the value from a first
            newList.append(a[count1])
            newList.append(b[count2])
            count1, count2 = count1 + 1, count2 + 1       #update the counter on each

    if count1 < len(a):                                  #if the while loop exited with left-over values in a, add them
        for f in range(count1, len(a)):
            newList.append(a[f])
    elif count2 < len(b):                                #do the same for b - the values are already in order so you're good
        for k in range(count2, len(b)):
            newList.append(b[k])

    return newList


def main():
    len = 100 * 1000
    arr1 = get_random_integer_array(len)
    arr2 = arr1[:]
    arr3 = arr1[:]

    start = milliseconds()
    iterative_mergesort(arr1)
    end = milliseconds()

    print "iterative_mergesort in", end - start, "milliseconds."

    start = milliseconds()
    mergeSortAlgorithm(arr2)
    end = milliseconds()

    print "mergeSortAlgorithm in", end - start, "milliseconds."

    start = milliseconds()
    arr3.sort()
    end = milliseconds()

    print "Python sort in", end - start, "milliseconds."

    print arr1 == arr3
    print arr2 == arr3

if __name__ == "__main__":
    main()