msd.py

"""
   Execution:  python msd.py < input.txt

   Data files:   https://algs4.cs.princeton.edu/51radix/words3.txt

   % python msd.py < words3.txt
   all
   bad
   bed
   bug
   dad
   ...
   yes
   yet
   zoo
"""


class MSD:
    R = 256  # extended ASCII alphabet size
    CUTOFF = 15  # cutoff to insertion sort

    def __init__(self, a):
        self.aux = ["" for _ in range(len(a))]
        self.sort(a, 0, len(a)-1, 0)

    def sort(self, a, lo, hi, d):
        if hi <= lo + self.CUTOFF:
            self.insertion(a, lo, hi, d)
            return

        count = [0 for _ in range(self.R+2)]
        for i in range(lo, hi+1):
            count[self.char_at(a[i], d)+2] += 1
        for r in range(self.R+1):
            count[r+1] += count[r]
        for i in range(lo, hi+1):
            self.aux[count[self.char_at(a[i], d)+1]] = a[i]
            count[self.char_at(a[i], d)+1] += 1
        for i in range(lo, hi+1):
            a[i] = self.aux[i-lo]
        for r in range(self.R):
            self.sort(a, lo+count[r], lo+count[r+1]-1, d+1)

    def insertion(self, a, lo, hi, d):
        for i in range(lo, hi+1):
            j = i
            while j > lo and a[j][d] < a[j-1][d]:
                a[j], a[j-1] = a[j-1], a[j]
                j -= 1

    def char_at(self, s, d):
        return ord(s[d])


if __name__ == '__main__':
    import sys
    words = []
    for line in sys.stdin:
        words.extend(line.split())
    MSD(words)
    for item in words:
        print(item)