Anonymous Anonymous - 1 month ago
205 0

Merge sort algorithm implemented in python with timer - reads list from external file.

Python

Python Merge Sort

#!/usr/bin/python
import time

def mergeSort(subject):
    if len(subject)>1:
        middlePos = len(subject)//2
        leftList = subject[:middlePos]
        rightList = subject[middlePos:]

        mergeSort(leftList)
        mergeSort(rightList)

        leftIndex = 0
        rightIndex = 0
        subjectIndex = 0

        while leftIndex < len(leftList) and rightIndex < len(rightList):
            if leftList[leftIndex] < rightList[rightIndex]:
                subject[subjectIndex] = leftList[leftIndex]
                leftIndex = leftIndex + 1
            else:
                subject[subjectIndex] = rightList[rightIndex]
                rightIndex = rightIndex + 1
            subjectIndex = subjectIndex + 1

        while leftIndex < len(leftList):
            subject[subjectIndex] = leftList[leftIndex]
            leftIndex = leftIndex + 1
            subjectIndex = subjectIndex + 1

        while rightIndex < len(rightList):
            subject[subjectIndex] = rightList[rightIndex]
            rightIndex = rightIndex + 1
            subjectIndex = subjectIndex + 1

fileName = raw_input("Enter filename to search: ")
content = [line.rstrip('\n') for line in open(fileName)]
content = map(int, content)

startTime = time.clock()
mergeSort(content)
endTime = time.clock()
duration = endTime - startTime


print len(content)
print duration