Java: sort List from index to index

Question

For arrays there is a special function for sorting a part of the array from index to index:

Arrays.sort(Object[] a, int fromIndex, int toIndex)

For List< T>

there is also a function for sorting

Collections.sort(List<T> list)

Unluckily there is no variant accepting a fromIndex and toIndex parameter.

I know that I could solve this problem by either applying

• Convert the List into an array and apply Arrays.sort, then convert it back to a List
• Copying the list entries indexed by fromIndex to toIndex to a new List (by using list.subList(fromIndex, toIndex)), sort it and overwrite the old list entries

But I hope there is a prettier way to do that.

Answer 1

Just use .subList() to get a "backed" view onto the main list, then call sort. The sublist is "write-through" so changes are reflected in the original.

List<Integer> foo = Arrays.asList(5,3,1,6,2,1);
Collections.sort(foo.subList(0, 3)); // sort first 3 elements 
System.out.println(foo);
Collections.sort(foo.subList(3, 6)); // sort last 3 elements
System.out.println(foo);

Output

[1, 3, 5, 6, 2, 1]
[1, 3, 5, 1, 2, 6]

Answer 2

You can use subList() on your original list, then sort the sublist and it will reflect on your original list without having to write back.

Answer 3

Copying the list entries indexed by fromIndex to toIndex to a new List (by using list.subList(fromIndex, toIndex)), sort it and overwrite the old list entries

No, there is no object copy when you call list.subList. The function subList creates a view backed by the original list. Only reference copies; no actual object copies.

Any operations (sorting) on the view will be reflected on the original list.

 public static void main(String[] args) throws Exception {
    List<Integer> list = Arrays.asList(1, 9, 8 ,7, 2, 3, 4);

    // [9, 8 ,7] => [7, 8, 9]
    sortList(list, 1, 4);

    System.out.println(list);       // [1, 7, 8, 9, 2, 3, 4]
  }

  public static <T extends Comparable<T>> void sortList(
      List<T> list, int fromIndex, int toIndex) {
    Collections.sort(list.subList(fromIndex, toIndex));
  }

Answer 4

Looking at the Oracle documentation, Collections and List simply do not contain this functionality, like the Arrays do. If I had to choose between your two suggestions, I'd implement the second one, using the List.subList(fromIndex, toIndex)).

Here's the docs: http://docs.oracle.com/javase/7/docs/api/java/util/List.html
http://docs.oracle.com/javase/7/docs/api/java/util/Collection.html
http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html