Demo entry 6498566

Merge Sort

   

Submitted by anonymous on May 30, 2017 at 08:48
Language: Python 3. Code size: 1.6 kB.

'''
References: 1. https://gist.github.com/m00nlight/a076d3995406ca92acd6
'''

import random
import time


def in_place_merge_sort(xs):
    unit = 1
    while unit <= len(xs):
        h = 0
        for h in range(0, len(xs), unit * 2):
            l, r = h, min(len(xs), h + 2 * unit)
            mid = h + unit
            # merge xs[h:h + 2 * unit]
            p, q = l, mid
            while p < mid and q < r:
                if xs[p] < xs[q]:
                    p += 1
                else:
                    tmp = xs[q]
                    xs[p + 1: q + 1] = xs[p:q]
                    xs[p] = tmp
                    p, mid, q = p + 1, mid + 1, q + 1

        unit *= 2

    return xs


def merge(l, r):
    l_i, r_i = 0, 0
    result = []
    while l_i < len(l) and r_i < len(r):
        if l[l_i] < r[r_i]:
            result.append(l[l_i])
            l_i += 1
        else:
            result.append(r[r_i])
            r_i += 1
    result += l[l_i:]
    result += r[r_i:]
    return result


def auxiliary_merge_sort(a):
    if len(a) <= 1:
        return a
    m = int(len(a) / 2)
    left = auxiliary_merge_sort(a[:m])
    right = auxiliary_merge_sort(a[m:])
    return merge(left, right)


if __name__ == '__main__':
    lst = [random.randint(0, i) for i in range(5)]

    start_time = time.time()
    print(auxiliary_merge_sort(lst))
    print("--- %s seconds ---" % (time.time() - start_time))

    start_time = time.time()
    print(in_place_merge_sort(lst))
    print("--- %s seconds ---" % (time.time() - start_time))

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).