gistfile1.txt

class MSDStringSort:
	def __init__(self):
		self._r = 256
		self._m = 15
		self.aux = None

	def _charAt(self,string,d):
		if string is None:
			return -1
		if d < len(string):
			return ord(string[d])
		else:
			return -1

	def sort(self,strings):
		n = len(strings)
		self.aux = [None] * (n+1)
		self._sort(strings,0,n-1,0)

	def _sort(self,strings,lo,hi,d):
		print('hi and lo are:',hi,lo)
		if hi <= lo + self._m:
			Insertion(strings,lo,hi,d)
			return

		count = [0] * (self._r+2) 

		for i in range(lo,hi+1):
			count[self._charAt(strings[i],d)+2] += 1

		for x in range(self._r+1):
			count[x+1] += count[x]

		for j in range(lo,hi+1):
			self.aux[count[self._charAt(strings[j],d)+1]] = strings[j]
			count[self._charAt(strings[j],d)+1] += 1

		for w in range(lo,hi+1):
			strings[w] = self.aux[w-lo]

		for r in range(self._r):
			self._sort(strings,lo+count[r],lo + count[r+1]-1,d+1)

class Insertion:

	def __init__(self,strings,lo,hi,d):
		self._sort(strings,lo,hi,d)

	def _sort(self,strings,lo,hi,d):
		i = lo
		while (i <= hi):
			j = i
			while (j > lo and self._less(strings[j], strings[j-1],d)):
				self._exchange(strings,j,j-1)
				j -= 1 

			i+= 1

	def _exchange(self,strings,a,b):
		w = strings[a]
		strings[a] = strings[b]
		strings[b] = w 

	def _less(self,a,b,d):
		return a[d:] < b[d:]

#for testing puroses use this list
#y = ['I','need','a','sentance','that','will','produce','a','sentance', 'at','least','twenty',
#	'characters','long','this','is','currently','fifteen','foot','long']