In this assignment you will implement two algorithms for sorting positive integers and compare their running times.

You are asked to implement algorithms with different worst case running times. 1. One of Insertion sort or selection sort, which are (n2). 2. One of Mergesort or Heapsort, which are (n log n).

.

(n log n) algorithm

(n2) algorithm

Input and output format

We will test your data on .txt files where the first column will contain positive integers and the second column will contain strings of length at most 20

Here is an example: 7 Alex

3 Maya 8 Steve 87 David 2 Mike

Your program should then sort the data based on the first column and output the results to the screen: 2 Mike

3 Maya 7 Alex 8 Steve 87 David

Given a text file data.txt, we will run your algorithms as follows: insertionsort data.txt

selectionsort data.txt

mergesort data.txt

heapsort data.txt