"David Hláčik" <da...@hlacik.eu> writes: > Hi guys, > > i am really sorry for making offtopic, hope you will not kill me, but > this is for me life important problem which needs to be solved within > next 12 hours.. > > I have to create stable algorithm for sorting n numbers from interval > [1,n^2] with time complexity O(n) . > > Can someone please give me a hint. Would be very very thankful! > > Thanks in advance! > D.
I don't have an algorithm but I have an implementation :) def sort2(numbers): "sort n positive integers in O(n) provided that they are all < n^2" N = len(numbers) units = [[] for i in xrange(N)] tens = [[] for i in xrange(N)] for n in numbers: units[n % N].append(n) for l in units: for n in l: tens[n / N].append(n) return [n for l in tens for n in l] -- Arnaud -- http://mail.python.org/mailman/listinfo/python-list