Python counting-sort of each input line (named file or stdin) Counting sort is NOT a comparison sort - O(N+k) - very fast. Reasonable memory use as it's only working with linesize*2 + k (k=256 - i.e. all possible values of a byte)

countsort.py

#!/usr/bin/python
#
# program that does a counting sort of input lines
#
# author: Paul Reiber
# 

import sys

def countsort(A,k):

    l = len(A)-1  # ignore carriage return
    result = [0] * l
    count = [0] * k

    for j in range(0,l):
        o = ord(A[j])
        count[o] = count[o] + 1

    for i in range(0,k):
        count[i] = count[i]+count[i-1]

    for n in range(l-1,-1,-1):
        c = count[ord(A[n])]
        result[c-1] = A[n]
        count[ord(A[n])] = c-1
    
    return ''.join(result)

f = sys.stdin
if len(sys.argv) > 1:
    f = open(sys.argv[1])

for line in f:
    print countsort(line,256)