What's wrong with Collections.sort?

Question

I have these strings in an ArrayList of String in no particular order but when I invoke Collections.sort(listReference), the sorted result is incorrect, why do 10 and 11 (the last 2 characters) come before 07, 08, 09?

12880  20090506054200001
12880  20090506054200002
12880  20090513070200003
12880  20090513070200004
12880  20090520202600005
12880  20090520202600006
12880  20090520232900010
12880  20090520232900011
12880  20090520232900007
12880  20090520232900008
12880  20090520232900009

Answer 1

It works fine for me:

import java.util.*;

public class Test {

      public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<String>();
        list.add("12880  20090506054200001");
        list.add("12880  20090506054200002");
        list.add("12880  20090513070200003");
        list.add("12880  20090513070200004");
        list.add("12880  20090520202600005");
        list.add("12880  20090520202600006");
        list.add("12880  20090520232900010");
        list.add("12880  20090520232900011");
        list.add("12880  20090520232900007");
        list.add("12880  20090520232900008");
        list.add("12880  20090520232900009");

        Collections.sort(list);

        for (String x : list) {
          System.out.println(x);
        }
      }
    }

Output:

12880  20090506054200001
12880  20090506054200002
12880  20090513070200003
12880  20090513070200004
12880  20090520202600005
12880  20090520202600006
12880  20090520232900007
12880  20090520232900008
12880  20090520232900009
12880  20090520232900010
12880  20090520232900011

Are you absolutely sure that your 7/8/9 entries don't have something "odd" in them elsewhere (e.g. a different element of whitespace between 12880 and the timestamp)?

If not, can you produce a short but complete program that demonstrates the problem?

Answer 2

Think there must be a problem with your code, it shouldn't sort like that. Can you post what you are doing?

See the following example

import java.util.Arrays;
import java.util.Collections;
import java.util.List;


public class Sort {

    public static void main(String[] args) {
     List list = Arrays.asList(
      "12880  20090506054200001",
      "12880  20090506054200002",
      "12880  20090513070200003",
      "12880  20090513070200004",
      "12880  20090520202600005",
      "12880  20090520202600006",
      "12880  20090520232900010",
      "12880  20090520232900011",
      "12880  20090520232900007",
      "12880  20090520232900008",
      "12880  20090520232900009"
      );

     Collections.sort(list);
     System.out.println(list);
    }
}

Answer 3

The two ending in 10 and 11 probably have tabs instead of spaces for the whitespace. Tabs are sorted before spaces.

Update: I actually tried this and the ones with the tabs sort right to the top of the order, which makes sense. So the tab theory doesn't actually explain the observed behavior.

Answer 4

Okay, let's start with the basic premise that Collections.sort works (see "select" isn't broken).

Your strings should not sort that way, and so far several people have confirmed that they do not. So what could be causing yours to sort like that?

• Did you pass a custom Comparator to sort()?
• Are the strings really exactly like you showed? Are the whitespace characters all spaces?

Can you post the exact code that produces this result?

Answer 5

Works fine for this unit test?

import static org.junit.Assert.*;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import org.junit.Test;

public class SortTest {

    List<String> expectedList = Arrays.asList(
      "12880  20090506054200001",
      "12880  20090506054200002",
      "12880  20090513070200003",
      "12880  20090513070200004",
      "12880  20090520202600005",
      "12880  20090520202600006",
      "12880  20090520232900007",
      "12880  20090520232900008",
      "12880  20090520232900009",
      "12880  20090520232900010",
      "12880  20090520232900011");

    @Test
    public void testSort() {
        List<String> stringList = new ArrayList(expectedList);
        Collections.shuffle(stringList);
        // comment following line out, for the rare case that shuffle returns the original list
        // assertFalse(stringList.equals(expectedList));
        Collections.sort(stringList);
        assertTrue(stringList.equals(expectedList));  
    }
}

Answer 6

I found out why it was behaving that way.

I was sorting the collections prior doing the String.format("%03d", sequence). Where sequence is the last 3 characters of each line above.

In summary,

1. sorting the String when the last characters were ... 7 8 9 1(0) 1(1).
2. (after doing the sort) writing it in the form 007, 008, 009, 010, 011.