# Python Implementations and Comparison of InsertionSort, SelectionSort, MergeSort and QuickSort

Python3 implementations with timing.

```#!/usr/bin/env python

from collections import deque
import random
import time

### INSERTION SORT ###
def InsertionSort ( unsorted ):
sorted = [ unsorted[0] ]
for i in range(1, len(unsorted)):
j = 0
while j < len(sorted) and sorted[j] < unsorted[i]:
j += 1
sorted.insert(j, unsorted[i])
# print ( ''.join(sorted) )
return sorted

### SELECTION SORT ###
# based on creating a new sorted list by extracting elements from the unsorted list
def SelectionSort1 ( unsorted ):
sorted = []
for j in range( len(unsorted) ):
smallest = max(unsorted)
for i in range( len(unsorted) ):
if unsorted[i] <= smallest:
smallest = unsorted[i]
position = i
sorted.append(smallest)
del unsorted[position]
return sorted

# based on swapping elements
def SelectionSort2 ( array ):
for i in range( len(array) ):
smallest = i
for j in range( i+1, len(array) ):
if array[j] < array[smallest]:
smallest = j
array[i], array[smallest] = array[smallest], array[i]
return array

### MERGESORT ###
def Merge ( array, lo, md, hi ):
queue1 = deque(array[lo:md+1])
queue2 = deque(array[md+1:hi+1])

pos = lo
while len(queue1) and len(queue2):
if queue1[0] < queue2[0]:
array[pos] = queue1.popleft()
else:
array[pos] = queue2.popleft()
pos += 1

while len(queue1):
array[pos] = queue1.popleft()
pos += 1
while len(queue2):
array[pos] = queue2.popleft()
pos += 1

def MergeSort ( array, lo, hi ):
if hi > lo:
md = int ((hi+lo)/2)
MergeSort ( array,lo,md )
MergeSort ( array,md+1,hi )
Merge ( array, lo, md, hi )

### QUICKSORT ###
def Partition ( array, lo, hi ):
# print ( ''.join(array[lo:hi+1]) )
pivot = array[hi]

pivotPosition = lo
for i in range ( lo, hi ):
if array[i] < pivot:
array[pivotPosition], array[i] = array[i], array[pivotPosition]
pivotPosition += 1

array[pivotPosition], array[hi] = array[hi], array[pivotPosition]
# print ( ''.join(array[lo:hi+1]) )
return pivotPosition

def QuickSort ( array, lo, hi ):
# avoid problems for almost sorted data
if lo == 0 and hi == len(array) - 1:
random.shuffle ( array )
if hi > lo:
pivotPosition = Partition ( array, lo, hi )
QuickSort ( array, lo, pivotPosition-1 )
QuickSort ( array, pivotPosition+1, hi )

### MAIN ###
if __name__ == "__main__":
# unsorted = [ 'T', 'H', 'I', 'S', 'L', 'I', 'S', 'T', 'I', 'S', 'U', 'N', 'S', 'O', 'R', 'T', 'E', 'D' ]
# print ( ''.join(unsorted) )
N = 20000

unsorted = [int(random.random() * N) for i in range(N)]
start = time.time()
sorted = InsertionSort( unsorted )
print ( "InsertionSort:  " + str( time.time() - start ) )
# print ( ''.join(sorted) )

unsorted = [int(random.random() * N) for i in range(N)]
start = time.time()
sorted = SelectionSort1( unsorted )
print ( "SelectionSort1: " + str( time.time() - start ) )
# print ( ''.join(sorted) )

unsorted = [int(random.random() * N) for i in range(N)]
start = time.time()
sorted = SelectionSort2( unsorted )
print ( "SelectionSort2: " + str( time.time() - start ) )
# print ( ''.join(sorted) )

array = [int(random.random() * N) for i in range(N)]
start = time.time()
MergeSort( array, 0, len(array)-1 )
print ( "MergeSort:      " + str( time.time() - start ) )
# print ( ''.join(array) )

array = [int(random.random() * N) for i in range(N)]
start = time.time()
QuickSort( array, 0, len(array)-1 )
print ( "QuickSort:      " + str( time.time() - start ) )
# print ( ''.join(array) )
```