2.1 Insertion Sort

import unittest
import random

def mysort(unsortedList):

# Introduction To Algorithms, 2nd Edition
# 2.1 Insertion Sort
for i in range(1, len(unsortedList)):
j = i - 1

# Python can swap two variables without using a third.
# Hence there is no need for the "key" variable shown in the page 17 pseudocode.
while (j >= 0 and unsortedList[j] > unsortedList[j+1]):
unsortedList[j], unsortedList[j+1] = unsortedList[j+1], unsortedList
[j]
j = j - 1
return unsortedList


class TestSortFunctions(unittest.TestCase):

def setUp(self):
self.seq = range(10)

def testsort(self):
for i in range(25):
random.shuffle(self.seq)
self.assertEqual(mysort(self.seq), range(10))

if __name__ == '__main__':
unittest.main()