# Java: Sorting Arrays

## Why you shouldn't write your own sort

A favorite computer science topic it sorting, putting a collection of data in some order. Typically this is done for arrays. Textbooks cover both the slow, O(n2), sorts (eg, selection, insertion, and bubble sorts) and fast, O(n log n), sorts (quick sort, heap sort, etc). These are interesting problems, give students a lot of practice with arrays, bring up important tradeoffs, and are generally quite educational.

However, the Java library already has sort methods that are more efficient, more general, and more correct than anything you are likely to write yourself. And they are already written. Professional programmers use one of the `java.util.Arrays.sort()` methods; they do not write their own, except perhaps in unusual cases.

Other data structures. There are sort methods in the `java.util.Collections` class which can be used to sort other kinds of data structures (eg, ArrayList), and there are data structures such as `TreeMap` that keep elements sorted based on a key.

## Sorting Arrays with `Arrays.sort(...)`

The `java.util.Arrays` class contains a number of static methods for sorting arrays, both arrays of primitive types and Object types. The sort method can be applied to entire arrays, or only a particular range.

Method | Description
--- | ---
Arrays sort methods
`Arrays.sort(pa);` | Sorts the elements of the array of a primitive type into ascending order using their natural ordering.
`Arrays.sort(pa, from, to);` | Sorts the elements pa[from]...pa[to-1] of a primitive type. into ascending order.
`Arrays.sort(oa);` | Sorts the elements of the array of an object type into ascending order, using the order defined by `Comparable` interface, which defines the `compareTo` method. Note that many Java classes such as `String` (but not `StringBuffer`), `Double`, `BigInteger`, etc implement `Comparable`.
`Arrays.sort(oa, from, to);` | Sorts the elements of the array, in the range from...to of an object type into ascending order.
`Arrays.sort(oa, comp);` | Sorts the elements of the array of an object type into ascending order, using the Comparator comp.
`Arrays.sort(oa, from, to, comp);` | Sorts the elements of the array, in the range from...to of an object type into ascending order using the Comparator comp.

## Example - Sorting a full array of doubles

This example sorts an entire array of objects. Because `Double` implements the `Comparable` interface (ie, defines the `compare()` method), there is no need to define a comparator. This sorts the entire array, but another version sorts in a specified subscript range.

      1
      2
      3
      4
      5
      6
      7
      8
      9
     10
     11
     12
     13
     14
     15
     16
     17
     18
     19
     20
    // arrays/-objectsort/Dblsrt.java
    // Fred Swartz 2003-09-15

    import java.util.*;

    public class Dblsrt {
        public static void main(String[] args) {
            Double[] da = {new Double(3.1), new Double(99), new Double(-66)};
            print(da);         // Print unsorted array.
            Arrays.sort(da);   // Sort array
            print(da);         // Print sorted array.
        }

        private static void print(Object[] oa) {
            for (int i=0; i<oa.length; i++) {
                System.out.print(oa[i] + " ");
            }
            System.out.println("");
        }
    }

## Comparators

All sorts that Java uses are comparison sorts, which means that they make all ordering decisions by comparing two values. If there is no natural ordering, or you don't want to use it, you can specify a Comparator to use in comparing two values. See Comparators.

## Sorting ArrayLists

In a similar way, you can use the methods below to sort ArrayLists.

       Collections.sort(alist);
       Collections.sort(alist, comparator);