main.py

import random
import time


def merge_sort(numbers, start, end):
    if start == end:
        return
    pivot_index = start + (end-start)//2
    merge_sort(numbers, start, pivot_index)
    merge_sort(numbers, pivot_index+1, end)
    i = start
    j = pivot_index+1
    result = []
    while i <= pivot_index and j <= end:
        if numbers[i] <= numbers[j]:
            result.append(numbers[i])
            i += 1
        else:
            result.append(numbers[j])
            j += 1
    if i <= pivot_index:
        result.extend(numbers[i:pivot_index+1])
    if j <= end:
        result.extend(numbers[j:end+1])
    k=0
    for i in range(start, end+1):
        numbers[i] = result[k]
        k += 1


def coderodde_merge(source,
                    target,
                    source_offset,
                    target_offset,
                    left_run_length,
                    right_run_length):
    left_run_index = source_offset
    right_run_index = source_offset + left_run_length

    left_run_index_bound = right_run_index
    right_run_index_bound = right_run_index + right_run_length

    while left_run_index != left_run_index_bound and right_run_index != right_run_index_bound:
        if source[right_run_index] < source[left_run_index]:
            target[target_offset] = source[right_run_index]
            right_run_index += 1
        else:
            target[target_offset] = source[left_run_index]
            left_run_index += 1
        target_offset += 1

    while left_run_index != left_run_index_bound:
        target[target_offset] = source[left_run_index]
        target_offset += 1
        left_run_index += 1

    while right_run_index != right_run_index_bound:
        target[target_offset] = source[right_run_index]
        target_offset += 1
        right_run_index += 1


def coderodde_mergesort_impl(source,
                             target,
                             source_offset,
                             target_offset,
                             range_length):
    if range_length < 2:
        return

    left_run_length = range_length // 2
    right_run_length = range_length - left_run_length

    coderodde_mergesort_impl(target,
                             source,
                             target_offset,
                             source_offset,
                             left_run_length)

    coderodde_mergesort_impl(target,
                             source,
                             target_offset + left_run_length,
                             source_offset + left_run_length,
                             right_run_length)

    coderodde_merge(source,
                    target,
                    source_offset,
                    target_offset,
                    left_run_length,
                    right_run_length)


def coderodde_mergesort(array, start, end):
    range_length = end - start

    if range_length < 2:
        return

    aux = [array[index] for index in range(start, end)]
    coderodde_mergesort_impl(aux, array, 0, start, range_length)


def coderodde_mergesort_all(array):
    coderodde_mergesort(array, 0, len(array))


def create_random_int_array(length):
    random.seed(1)
    return [random.randint(-1000000, 1000000) for _ in range(length)]


def get_ms():
    return int(round(time.time() * 1000))


def same(arr1, arr2):
    for index in range(len(arr1)):
        if arr1[index] != arr2[index]:
            return False
    return True


if __name__ == "__main__":
    arr1 = create_random_int_array(1000 * 1000)
    arr2 = arr1[:]

    start_from = 10
    end_at = len(arr1) - 10

    start = get_ms()
    merge_sort(arr1, start_from, end_at)
    end = get_ms()

    print "OP mergesort in", (end - start), "milliseconds."

    start = get_ms()
    coderodde_mergesort(arr2, start_from, end_at + 1)
    end = get_ms()

    print "coderodde mergesort in", (end - start), "milliseconds."
    print "Algorithms agree:", same(arr1, arr2)