# 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.