sort : Java Glossary

Putting items in ascending or descending order by key fields. The English language meaning of sort is simply to categorise, e.g. to put all your bills into folders by category, e.g. all the electric bills together, all the phone bills together. An internal sort is done strictly in RAM (Random Access Memory). An external sort uses hard disk temporary files. A sort is stable if it naturally preserves existing order when you have duplicate keys. If you want existing order preserved and you are using an unstable sort, you must add an extra sequence number key to your records and use that as a secondary tie-breaking key.

Internal Sort

In the Java version 1.2 or later there are built-in sorts such as Arrays.sort and Collections.sort See java.util.Comparator and java.util.Comparable for different sorting orders. For String sorting in various international orders see java.text.Collator, java.text.RuleBasedCollator and java.text.CollationKey.

In

import java.util.Arrays;
//...
// works for:
// int[] myArray;
// Object[] myArray;
// Dog[] myArray;
// byte[] myArray;
// etc.
Arrays.sort( myArray );

import java.util.ArrayList;
import java.util.Collections;
...
Collections.sort( myArrayList );

Note that there is no such method as ArrayList.sort.

Gotchas

• Though it is called Collections.sort, the fool thing cannot sort arbitrary Collections. It can only sort Lists. It should have been called  Lists.sort.
• The sort method is not part of the Collection interface. It lives in the Collections class. So you cannot say myCollection. sort(). You must say Collections.sort( myCollection ); However, sort will not work on Collections generally, only Lists.
• Collections.sort will not work on arrays. You must use Arrays. sort.

Comparators

return -( (String )a ).compareTo( (String)b );

If you need a Comparator for sorting Strings in a case-insensitive way, you can use the pre-build Comparator String.CASE_INSENSITIVE_ORDER. It is effectively the same as if you had asked the Comparable/Comparator Cutter Amanuensis to

Predefined Comparators

You don’t always have to write your own Comparator. Oracle provides some predefined ones such as String.CASE_INSENSITIVE_ORDER. This is a Comparator, though it is a constant, namely a static final member of the String class that can only be used to sort Strings.

There is also Collections.reverseOrder (Comparator) which can take any Comparator and create one that sorts in reverse order.

Comparables

Sorting Speed

In the following table, speed is measured relative to RadixSort on a 100,000 item set of 5-character random keys of the form A9999 where SunSort is arbitrarily assigned 100. Tests done under Java 1.4.1 java.exe on a 233 MHz Pentium 128 MB RAM. Bigger is better.

External Sort

Abundance uses Op-Tech sort. It rolls itself out to disk, calls in Opt-Tech sort, giving it all of RAM, then rolls itself back in.

You can find various sorts that can handle data too big to fit in RAM by googling for Java big sort. Usually such big sorts use an N-way Merge Sort algorithm.

Merge Sort

You might experiment with a merge sort to use on a multi-core CPU (Central Processing Unit). You split the data into separate datasets and sort each on a separate threads then merge the results in a single pass.

Tag Sort

1. Combine the two arrays into one, with objects having two or more fields. Write a Comparator or implement Comparable for these new combined objects.
2. Sorts don’t actually sort the records, they just order an array of references. The objects themselves don’t move. If the things you are sorting are not collected nicely together into objects you can use a tag sort. Tag records are short records consisting of the sorting key fields plus a reference back to the original record. This reference may be an array index or a pointer to the original object. The tag records need not contain any data at all, just a way to find it when the comparator is called.

Bad Sorts

One is a selection sort:

1. Select the largest of the N keys and move its record to the output area.

2. Select the largest of the remaining N-1 keys and move its record to the output area. etc.

Another is the bubble sort, where you pairwise swap elements in a pass through all the elements to percolate the biggest element to the top. Then repeat for the list not containing the biggest elements so far. etc.

A variant of the bubble sort, that is a tiny bit faster is the bi-directional sort that percolates the smallest element to the bottom and the biggest element to the top in alternating direction passes, gradually working toward the middle.

Another is the insertion sort, where you create a new list and gradually add to it, always keeping the new list in sorted order by inserting the new element in the place where it belongs. You find the place by binary search and slide all the subsequent elements down to make room for it. You sometimes have to use this type of sort when you don’t have all the elements at the start of the sort. They are just given to you one at a time and you want a sorted list immediately output after each element is added.

Ordered Collections

Descending/Inverse/Reverse Order with reverseOrder

Sorting ascending order means sorting with the small elements first then the big. This is usual ordering. Descending order means sorting with the big elements first then the small.

If you have a Comparator or Comparable of some kind, you can convert it into one that sorts into the reverse of the usual order, e. g. if the original sorts alphabetically, the new one will sort in reverse alphabetical order. Here is how you use it:

If you don’t have a suitable base Comparator, just write an ordinary Comparator from scratch and reverse the operands to each compare inside it, or return - result instead of result.

You can’t use Comparators or Collections.reverseOrder to sort arrays of primitives. How could you sort an array of ints in reverse order? Here are some ideas from the mind of Eric Sosman:

• Use Arrays.sort() to put the array in ascending order and then reverse it with a simple loop (swap [0]⇔[n-1], [1]⇔[n-2],… and so on).
• Use Arrays.sort() to put the array in ascending order and then read it backwards: Instead of looking at [0],[1],[2],… you look at [n-1],[n-2],[n-3],…
• Negate every element of the array, use Arrays.sort() to put the array in ascending order and then negate all the elements again. (Note that this won’t work if Integer.MIN_VALUE appears in the array because Integer.MIN_VALUE == -Integer.MIN_VALUE.) Negating it does not change the sign.

Ascending/Descending Arrow Indicators

• Up is ascending because ascending means climbing up. It has nothing to do with the order of the items on the page.
• Up is ascending because up connotes normal and happy and so does ascending.
• Up is ascending because the indicator represents the keyword the programmer gave to the SQL (Standard Query Language) sort to get items to paint top to bottom. He did not actually paint bottom to top for descending order. By default, you get ascending. When you talk of up and down, usually up is the default. So the two are associated by both being the default.
• Up is ascending because when things on the page are ordered in ascending order, you see the small easy numbers first then work toward the more difficult. Climbing up, i.e. ascending stairs, is the difficult direction.
• Up is ascending because ascending elevators and escalators go up.

• Down is ascending because the bigger items are at the bottom of the page.
• Down is ascending because down is the direction you read to see ever-bigger items.
• Down is ascending because the indicator means the direction of flow and of pull of gravity. It points downward toward the logical gravitation point attracting the bigger/heavier items.

• Is the icon an indicator of current state or a command to change to a desired state? Whatever you think the icon should be, others will think it should be the opposite be opposite. Perhaps the arrow does not tell you how things are, but how they will be if you click the icon. The icon represents a command to sort, not an indictor of how things are.

Ascending/descending icons

31 Variations on Ascending/Descending Icons for Sort Order
Name	Ascending	Descending	Size in Pixels	Votes	Notes
Alpha			29 × 27	4	This technique is clear for alphabetic sorts. You need a fairly big icon to make it readable. It would be paired with the numeric icon, also letting you know if you are getting an alpha or numeric collating sequence, or it could be used for both.
Arrow			12 × 16	0	Direction of pointing is opposite to Thunderbird.
Arrow and Bars			31 × 30	1	Arrow and bars.
Bars			16 × 15	1	The longer bars represent the bigger records.
Caret			16 × 12	0	Can be kept small. Direction of pointing is opposite to Thunderbird.
Climbing			16 × 16	0	This convention helps break the connection with reading direction and suggests the climbing association.
Crystal			21 × 19	0	Option for OpenOffice. Open Office allows you to scale the icons to various sizes. Largest variant shown here.
Dice			22 × 64	0	Bigger numbers on dice indicate direction. Needs to be quite large vertically.
Exclamation	!	¡	3 × 12	0	This can be done without images, using simple text. ¡ is ¡ or '\u00a1'
Dual			14 × 6	0	Direction of pointing is opposite to Thunderbird. It points up for ascending and gets fatter at the bottom to suggest bigger items are at the end of the list. The user will usually assume the ascending icon is on the left on matter what it looks like. You display a pair. The bright half of the pair indicates the current order. You click the icon anywhere to toggle the direction. You don’t have to click just in the dim triangle.
Galaxy			22 × 24	0	Default for Open Office. This technique similar to alpha, except the arrow always point down (Tango convention) and the icons are more compact. Open Office allows you to scale the icons to various sizes. Largest variant shown here.
Gnome			32 × 32	0	Like arrow with a side decoration.
Gradient			16 × 16	1	The more intense/darker side of the icon represents the bigger records. The ascending icon suggests the heavier records settling to the bottom.
High Contrast			22 × 26	0	Option for OpenOffice. Open Office allows you to scale the icons to various sizes. Largest variant shown here. Works best on a darker background.
Industrial			21 × 19	0	Option for OpenOffice. Open Office allows you to scale the icons to various sizes. Largest variant shown here.
Intellij			6 × 16	0	Used in JetBrains Intellij Idea IDE (Integrated Development Environment).
Mac OSX			7 × 7	0	Direction of pointing is opposite to Thunderbird. It points up for ascending and gets fatter at the bottom to suggest bigger items are at the end of the list.
Music			8 × 16	0	Musical sharp and flat. This can be done without images, using simple text if you have a font that supports them. Sharp is '\u266f' and flat is '\u266d'.
Numeric			30 × 28	2	This technique is clear for numeric sorts. You need a fairly big icon to make it readable. It would be paired with the alpha icon, also letting you know if you are getting an alpha or numeric collating sequence.
Ramp			16 × 7	0	Ascending/descending ramp. Ties nicely with the words ascending and descending. Also looks a bit like a graph. Might be confused with a volume control.
Stairs			15 × 12	2	Ascending/descending staircase. Ties nicely with the words ascending and descending.
Tango			31 × 29	1	Proposed Tango standard. Similar to arrow and bars. In Tango, the arrow always points down. Unfortunately, it takes up a fair bit of screen real estate to be legible.
Text	ascending	descending	81 × 15	0	ASCII (American Standard Code for Information Interchange) text. Takes up excessive horizontal space.
Thunderbird			8 × 7	0	This is the convention Thunderbird email uses to describe how data are currently sorted. Hard to see on a pale background because it has white elements. What you see here is an improved anti-aliased version of what Thunderbird itself uses. Unfortunately it points down for ascending and gets fatter at the top to suggest bigger items are at the top of the list. I think the intent is either: The arrow points in the direction of the ascending flow of the data. When you click the arrow, it will sort the data in that direction.
Thunder Triangle			16 × 14	0	Could be even smaller. Direction of pointing is same as Thunderbird. Unfortunately it points down for ascending and gets fatter at the top to suggest bigger items are at the top of the list.
Thunder Triangle (small)			8 × 7	0	Direction of pointing is same as Thunderbird. Unfortunately it points down for ascending and gets fatter at the top to suggest bigger items are at the top of the list.
Triangle			16 × 14	2	Direction of pointing is opposite to Thunderbird. It points up for ascending and gets fatter at the bottom to suggest bigger items are at the end of the list. The problem with any of the triangle based icons is there are two established contradictory conventions loose in the world. Neither is about to die soon. You are thus guaranteed to confuse people since they must deal with both in the course of a day. That is too bad. The triangle is easy to read even in tiny renderings.
Triangle (small)			8 × 7	0	Direction of pointing is opposite to Thunderbird. It points up for ascending and gets fatter at the bottom to suggest bigger items are at the end of the list.
Turtle			30 × 19	0	Descending is associated with inverted. The descending icon has the unfortunate connotation of defunct.
Water Drop			16 × 24	0	The water drop falls down, with the fat part at the bottom.
Vista			4 × 7	0	Microsoft Windows Vista standard. A bit too small to see clearly. Direction of pointing is same as Thunderbird. Unfortunately it points down for ascending and gets fatter at the top to suggest bigger items are at the top of the list. Unfortunately it points down for ascending and gets fatter at the top to suggest bigger items are at the top of the list.

Please let me know at  † which one you like best so I can record your vote.

Perhaps some day the association and icon choices will be a configurable part of LAF (Look And Feel) so users will have consistent conventions across all the apps they use. Consistency is the problem. You can find variants by googling view-sort-ascending

I have found the majority up application use an upward arrow to indicate that items are currently displayed in ascending order. No matter what you do, you are going do it backwards for some people and irritate them. So you might use indicators that don’t have any arrows or at least no confusing up/down arrows. Let the user figure out what your colours or letters A/D mean for example.

You can clarify the meaning of your icons with tooltip help on the icon to say things like:

• Sort Ascending
• Sort Descending
• Sorted in Ascending order
• Sorted in Descending order
• Now in ascending order. Click to sort in descending order.
• Ascending order selected. Click to select descending order.

My current favourite is the gradient. It avoids the ambiguity of arrow direction conventions and has a nice physical metaphor. Perhaps I will have to make the icons configurable. Any convention would eventually work, if there were consensus, even something completely arbitrary would work. I am hoping this little essay will help form a consensus and encourage standardisation.

Generic Sorts

However, because of Java’s lack of orthogonality, your List sort won’t work for arrays of such Objects. You need to write very similar code to do that. Even that array version won’t sort an array of primitives such as long, int or byte. You have to write yet another slightly different version of the sort to handle each type of primitive.

Complete Example

Learning More