Skip to content

Instantly share code, notes, and snippets.

@icsaas
Created November 21, 2013 03:20
Show Gist options
  • Save icsaas/7575603 to your computer and use it in GitHub Desktop.
Save icsaas/7575603 to your computer and use it in GitHub Desktop.
simplest python k-way merging sort
import heapq
import random
import threading
#k thrads
k=4
#Generate n numbers for each thread to process.
n=10
def GenerateNumbers(a,b):
numbers=[]
for i in xrange(n):
numbers.append(random.randint(a,b))
return numbers
class SortingThread(threading.Thread):
def __init__(self):
super(SortingThread,self).__init__()
self.numbers=GenerateNumbers(1,100)
def run(self):
self.numbers.sort()
if __name__=='__main__':
#Parallel sort with multiple threads
#
sortingThreads=[]
for i in xrange(k):
sortingThreads.append(SortingThread())
for i in xrange(k):
sortingThreads[i].start()
for i in xrange(k):
sortingThreads[i].join()
print i,sortingThrads[i].numbers
#use heap to output the final sorted list.
#We fill the heap with serval numbers firstly
#
theHeap=[]
for i in xrange(1):
for t in xrange(len(sortingThreads)):
number=sortingThreads[t].numbers[i]
heapq.heappush(theHeap,number)
sortedNumbers=[]
#In the while loop,people may replace the code by reading file routeings.
#Since IO is always the bottleneck,so single thread should be enough
p=1
while (len(theHeap)>0):
if p<len(sortingThreads[t].numbers):
for t in xrange(len(sortingThreads)):
number=sortingThreads[t].numbers[p]
heapq.heappush(theHeap,number)
p+=1
sortedNumbers.append(heappop(theHeap))
#Done
print sortedNumbers
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment