Monthly
288 pp. per issue
6 x 9, illustrated
ISSN
0899-7667
E-ISSN
1530-888X
2014 Impact factor:
2.21

Neural Computation

November 1995, Vol. 7, No. 6, Pages 1188-1190
(doi: 10.1162/neco.1995.7.6.1188)
© 1995 Massachusetts Institute of Technology
Sorting with Self-Organizing Maps
Article PDF (128.52 KB)
Abstract

A self-organizing feature map (Von der Malsburg 1973; Kohonen 1984) sorts n real numbers in O(n) time apparently violating the O(n log n) bound. Detailed analysis shows that the net takes advantage of the uniform distribution of the numbers and, in this case, sorting in O(n) is possible. There are, however, an exponentially small fraction of pathological distributions producing O(n2) sorting time. It is interesting to observe that standard learning produced a smart sorting algorithm.