Skip to content

Instantly share code, notes, and snippets.

@JacquesLucke

JacquesLucke/iterative_merge_sort.py

Last active May 16, 2018 13:01
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save JacquesLucke/f9e0756bac9b0a2adca29572406f69ff to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save JacquesLucke/f9e0756bac9b0a2adca29572406f69ff to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. JacquesLucke created this gist May 16, 2018.
    43 changes: 43 additions & 0 deletions iterative_merge_sort.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,43 @@
    from math import ceil
    from random import randint

    def mergesort(A):
    B = [None] * len(A)
    chunk_size = 1
    while chunk_size < len(A):
    for i in range(ceil(len(A) / chunk_size / 2)):
    merge(A, B,
    start1 = 2 * i * chunk_size,
    start2 = min((2 * i + 1) * chunk_size, len(A)),
    end = min((2 * i + 2) * chunk_size, len(A)))
    A[:] = B
    chunk_size *= 2

    def merge(src, dst, start1, start2, end):
    i = start1
    j = start2
    for index in range(start1, end):
    if j == end:
    dst[index] = src[i]
    i += 1
    elif i == start2:
    dst[index] = src[j]
    j += 1
    elif src[i] <= src[j]:
    dst[index] = src[i]
    i += 1
    else:
    dst[index] = src[j]
    j += 1

    array = list(map(int, input().split()))
    mergesort(array)
    print(array)

    def get_random_numbers(n):
    return [randint(0, 50) for _ in range(n)]

    # for _ in range(10):
    # array = get_random_numbers(30)
    # mergesort(array)
    # print(array)