sorting - How to sort colors properly?

I can't seem to be able to sort colors by their hue and perceptual brightness correctly. Here's my current solution, but it's not right; there are all these dark bands:

c = RandomColor[RGBColor[_, _, _], 500];
o1 = SortBy[c, ColorConvert[#, "HSB"][[1]] &];
o2 = SortBy[c, ColorConvert[#, "LAB"][[2]] &];
Image[#, ImageSize -> 400] & /@ {Table[o1, {100}], Table[o2, {100}]}

I want to find a way to achieve color sorting that minimizes these bands and smooths the transition along the gradient, something similar to the clustering histograms Theo Gray used in the Disney app.

Answer

If you're looking for a way to sort the colors in such a way as to make them seem the least discontinuous, then one way to think of it is that each color is a point in a space endowed with a distance metric (either the CIELAB 1976 or the CIELAB2000 perceptual metrics), and you are trying to find a shortest tour that visits each point. We can do that with ColorDistance and FindShortestTour:

c = RandomColor[500];
ord2000 = 
  FindShortestTour[c, 
    DistanceFunction -> (ColorDistance[#1, #2, 
        DistanceFunction -> "CIE2000"] &)][[2]];

ord76 = FindShortestTour[c, DistanceFunction -> ColorDistance][[2]];
Image[Table[c[[ord2000]], {100}]]
Image[Table[c[[ord76]], {100}]]

Giving the following two results:

To my eye, it looks like the CIE2000 metric does a slightly better job than the older 1976 variant.

As Mr. Wizard points out, "sorting" colors is sort of like "sorting" random points in a space with more than one dimension: there's no general way to do it that makes sense, since you're trying to impose a linear order on something which has more than one dimension. So the best you can do is find a shortest tour.