Skip to content

Instantly share code, notes, and snippets.

@m00nlight
Last active August 29, 2015 14:14
Show Gist options
  • Save m00nlight/f07689808e88a4fd125f to your computer and use it in GitHub Desktop.
Save m00nlight/f07689808e88a4fd125f to your computer and use it in GitHub Desktop.
Python count sort
def count_sort(A, K):
""" A is positive integer array each element is in range [0, K]"""
count = [0] * (K + 1)
for a in A:
count[a] += 1
for i in range(1, K + 1):
count[i] = count[i - 1] + count[i]
B = [None] * len(A)
for i in range(len(A) - 1, -1, -1):
B[count[A[i]] - 1] = A[i]
count[A[i]] -= 1
return B
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment