[SOLVED] data structure algorithm math python Q1 Sorting with duplicates (30 marks)

Q1 Sorting with duplicates (30 marks)

The input is a unsorted list of non-negative real numbers. The list has size $n$, and there are $k leq n$ different numbers in that list (i.e. there may be duplicates).

Q1.1 (25 marks)
Design and implement an algorithm which can sort this list and has average runtime in $O(n log k)$. You may only use the Python $list$ container, and no other (so no dictionary, no set, etc). You may not use an existing implementation of a sorting algorithm (including Pythons). If you feel that it is needed, you can write your own implementation of a sorting algorithm. Any other data structure that you need has to be implemented here as well. For reference, the solution code is less than 40 lines long.
In[0]:
def sortlist(l):
Returns a sorted list which contains the same elements as l
(including duplicates). The input list l should not be changed.
#TODO implement your algorithm here.
pass

We provide unit tests below. Your implementation must pass all tests to get full marks. For reference, the solution code runs in less than a minute. If your code requires a significant longer time to run, then it may be bugged, or your algorithm may not have an average runtime in $O(n log k)$.
In[0]:
import unittest
import random
import math
random.seed(a=0)

class Testsortlist(unittest.TestCase):
def setUp(self):
self.numbers = [math.sqrt(i) for i in random.sample(range(10000000), 1000)]
self.ntests = 100

def checklist(self, l):
check = sortlist(l)
l.sort()
self.assertEqual(l, check)

def testEmpty(self):
self.checklist([])

def testSingle(self):
self.checklist([0])

def testNoMult(self):
for _ in range(self.ntests):
self.checklist(random.sample(self.numbers, len(self.numbers)//2))

def testkMult(self):
for k in [2, 5, 10, 100]:
for _ in range(self.ntests):
self.checklist(random.choices(self.numbers, k=k*len(self.numbers)))
In[0]:
testlist = Testsortlist()
suite = unittest.TestLoader().loadTestsFromModule(testlist)
unittest.TextTestRunner().run(suite)

Q1.2 (5 marks)
Prove that your algorithm has an average runtime in $O(n log k)$. Determine and prove its worst-case runtime.

(write your answer here)