# QuickSort and MergeSort

## Code

import random
import sys
import time

sys.setrecursionlimit(1000000)

def quicksort(data, lo, hi):
if lo >= hi:
return
else:
x = data[lo]
i, j = lo, hi
while i < j:
while x <= data[j] and i < j:
j -= 1
data[i] = data[j]
while x >= data[i] and i < j:
i += 1
data[j] = data[i]
data[i] = x
quicksort(data, lo, i)
quicksort(data, i + 1, hi)

def mergesort(data, lo, hi):
pass
if lo >= hi - 1:
return
else:
mid = (lo + hi) // 2
mergesort(data, lo, mid), mergesort(data, mid, hi)
# merge(data, lo, mid, hi)
if not lo < mid < hi:
return
else:
result = list()
i, j = lo, mid
while i < mid and j < hi:
if data[i] <= data[j]:
result.append(data[i])
i += 1
else:
result.append(data[j])
j += 1
data[lo:hi] = result + data[i:mid] + data[j:hi]

data = [random.randint(0, 1000000) for i in range(20000)]
d1, d2 = (data.copy() for i in range(2))
start = time.time()
quicksort(d1, 0, len(data) - 1)
print('quicksort', time.time() - start)
start = time.time()
mergesort(d2, 0, len(data))
print('mergesort', time.time() - start)
start = time.time()
sorted(data)
print('timsort in C', time.time() - start)


## Result

quicksort 0.06924867630004883
mergesort 0.10277152061462402
timsort in C 0.0060214996337890625


# BinaryTreeSort

## Code

import random
from dsr import BinaryTreeNode as Node

class BinarySortTree(object):
def __init__(self, data=list()):
self.root = Node()
for val in data:
self.insert(val)

def insert(self, val):
if self.root.value is None:
self.root.value = val
return
leaf, root = (self.root,)*2
while root is not None:
leaf = root
if root.value > val:
root = root.left
else:
root = root.right
if leaf.value > val:
leaf.left = Node(val)
else:
leaf.right = Node(val)

def traverse(self, root=False):
if root is False:
root = self.root
if root is None:
return list()
return self.traverse(root.left) + [root.value] + self.traverse(root.right)

def __repr__(self):
return repr(self.root)

data = [random.randint(0, 100) for i in range(10)]
print(data)
tree = BinarySortTree(data)
print(tree)
print(tree.traverse())


## Result

[36, 43, 26, 9, 73, 76, 73, 72, 31, 19]
(36)
/    \
(26)            (43)
/    \               \
(9)           (31)                 (73)
\                              /    \
(19)                      (72)           (76)
/
(73)
[9, 19, 26, 31, 36, 43, 72, 73, 73, 76]