Sorting arranges elements according to a comparison rule. Understanding selection sort and insertion sort helps you reason about comparisons, movement, and loop invariants before using library sorting in real applications. Neither quadratic teaching algorithm is the default recommendation for large general-purpose data. This lesson explains both implementations, then shows Arrays.sort for practical use. The contract includes whether the input changes, which order is requested, and whether equal-key records must preserve their original order.
Selection sort chooses the next minimum
Selection sort divides the array into a sorted prefix and an unsorted suffix. For each position, it finds the minimum remaining element and swaps it into place. After that step, the prefix has gained its next correct element. It performs a quadratic number of comparisons even when the input is already sorted. The simple swap-based implementation uses constant auxiliary space and is generally not stable because swaps can reorder equal-key elements.
Insertion sort grows a sorted prefix
Insertion sort takes the next value and shifts larger preceding values one position right until the value fits. The prefix before the current position is already sorted, so the insertion preserves that property. The strict greater-than comparison leaves equal values in their earlier order, making this form stable. Its worst-case time is quadratic, but nearly sorted input requires fewer shifts, and already sorted input can be processed in linear time.
State time and space with the input case
An ascending array is a favorable case for insertion sort but does not remove selection sort's full minimum-search scans. A reverse-sorted array makes insertion sort move many elements. Both examples modify the array in place and use a fixed number of local variables. More advanced algorithms trade different worst-case, expected, stability, and memory properties. Compare those documented guarantees rather than choosing an algorithm solely because its code is shorter.
Use the library for production sorting
Arrays.sort supplies tested platform implementations for primitive arrays and object arrays. The algorithm and guarantees differ by overload and Java release, so do not describe all Java sorting as one universal algorithm. Object-array sorting has a stability contract; primitive values do not carry separate identity records whose equal-key order needs preservation. Collections and List sorting use comparator rules for objects. Choose the API matching the data representation and read its documented contract.
Compare merge sort, quicksort, and heap sort
| Algorithm | Time | Auxiliary space | Stable? |
|---|---|---|---|
| Merge sort | O(n log n) | O(n) for ordinary array merging | Yes, with an order-preserving merge |
| Quicksort | Expected O(n log n), worst O(n squared) | Expected O(log n), worst O(n) recursion stack | Usually no |
| Heap sort | O(n log n) | O(1) iterative array workspace | No |
Merge sort splits the input, sorts each half, and merges the sorted halves. Its extra array storage buys predictable time and a natural stability guarantee when equal elements are merged in their original order. Quicksort partitions around a pivot; a poor pivot strategy can repeatedly create unbalanced partitions and cause quadratic work. Heap sort builds a heap and repeatedly moves its selected extreme to the final array position. These are conventional array implementations: variants can change the space or stability properties. Choose according to the required guarantees rather than treating an algorithm name as a complete implementation contract.
Define a valid comparison rule
A Comparator must be consistent enough to establish an ordering. Use Integer.compare instead of subtracting arbitrary integer values, which can overflow and reverse a result. Compose comparisons with thenComparing when ties need a secondary key. Sorting by a key does not automatically remove duplicates. If equality and ordering differ, explain how that affects later use in sorted collections such as TreeSet rather than assuming sorting changes the objects' equals method.
Verify the result and preserve inputs deliberately
Check ascending order and that the output contains the same elements with the same counts. A sorted list missing one duplicated value is incorrect even if every adjacent pair is ordered. If callers need the original arrangement, clone the array before sorting. A stable sort is important when a previous ordering or record sequence must be retained for equal keys. The requirement should decide whether mutation, stability, or additional storage is acceptable.
Practice tasks and checks
Run both teaching sorts on an empty array, one element, sorted input, reverse-sorted input, and repeated values. Verify both order and element counts. Add comparison and shift counters to observe why insertion sort behaves differently on nearly sorted input. Do not present those counts as wall-clock timings. For object sorting, create records with a priority and label and use Comparator.comparingInt followed by thenComparing. Explain how equal priorities are ordered under the secondary rule. Finally, decide whether your application may mutate its input; test the clone-based approach if preserving the original matters. Keep stability, mutation, and auxiliary memory as separate properties instead of calling every successful sort equivalent.
Java Summary
- Sorting preserves elements and their counts while changing order.
- Stability and mutation are separate algorithm properties.
- Prefer documented library sorting for ordinary production work.
- Continue with complexity analysis when these examples are clear.
Java Examples
Each example shows the code, the output it produces and what each part does.
Implement selection sort
Save this program as SelectionSortDemo.java. Compile it with javac SelectionSortDemo.java and run it with java SelectionSortDemo.
Expected output:
At the first position, the search finds a two and swaps it with seven. Later passes place the remaining smallest values into the next positions. The inner loop starts after the current position because the prefix is already final. Swapping through a temporary variable avoids losing the displaced value. Both copies of two remain present, showing that sorting changes order rather than deduplicating the data.
import java.util.Arrays;
public class SelectionSortDemo {
static void sort(int[] values) {
for (int i = 0; i < values.length - 1; i++) {
int smallest = i;
for (int j = i + 1; j < values.length; j++) {
if (values[j] < values[smallest]) smallest = j;
}
int temp = values[i]; values[i] = values[smallest]; values[smallest] = temp;
}
}
public static void main(String[] args) {
int[] values = {7, 2, 5, 2};
sort(values);
System.out.println(Arrays.toString(values));
}
}[2, 2, 5, 7]Implement insertion sort
Save this program as InsertionSortDemo.java. Compile it with javac InsertionSortDemo.java and run it with java InsertionSortDemo.
Expected output:
The first insertion saves one, shifts six right, and places one at index zero. The second saves four, shifts six again, and places four between one and six. Saving value before shifting is essential because array assignments overwrite positions. The condition checks j before reading values[j], preventing a negative-index access. Using greater-than rather than greater-than-or-equal preserves the relative order of equal values in this algorithm.
import java.util.Arrays;
public class InsertionSortDemo {
static void sort(int[] values) {
for (int i = 1; i < values.length; i++) {
int value = values[i], j = i - 1;
while (j >= 0 && values[j] > value) {
values[j + 1] = values[j]; j--;
}
values[j + 1] = value;
}
}
public static void main(String[] args) {
int[] values = {6, 1, 4};
sort(values);
System.out.println(Arrays.toString(values));
}
}[1, 4, 6]Sort a copy using the library
Save this program as LibrarySortDemo.java. Compile it with javac LibrarySortDemo.java and run it with java LibrarySortDemo.
Expected output:
clone creates a separate primitive array containing the same values. Arrays.sort modifies that copy, leaving original in its initial order. The copy costs linear extra storage, a deliberate tradeoff for preserving input. If callers allow mutation, sorting the original directly avoids that copy. For arrays of object references, cloning the array copies references rather than deeply cloning each referenced object.
import java.util.Arrays;
public class LibrarySortDemo {
public static void main(String[] args) {
int[] original = {8, 3, 5};
int[] sorted = original.clone();
Arrays.sort(sorted);
System.out.println(Arrays.toString(original));
System.out.println(Arrays.toString(sorted));
}
}[8, 3, 5]
[3, 5, 8]Java FAQ
Is sorting the same as removing duplicates?
No. Sorting rearranges elements while preserving their multiplicities. Deduplication is a separate operation with its own equality and retention policy.
Why not always use selection sort?
It is useful for learning invariants, but it performs quadratic comparisons even for sorted input. Library sorting is generally a better default for real applications unless a specific measured requirement supports another choice.
Which sorting algorithm does Java use?
Arrays.sort on primitive arrays uses a dual-pivot quicksort, which is very fast on average. Sorting objects, with Arrays.sort on object arrays, Collections.sort or List.sort, uses TimSort, a stable merge sort variant that is especially quick on data that is already partly sorted.
What is a stable sort?
A stable sort keeps elements with equal keys in their original relative order. That matters when sorting by several fields in turn: sort orders by date, then stably by customer, and each customer's orders stay in date order. Insertion sort and merge sort are stable; selection sort and quicksort usually aren't.
Should I write my own sorting algorithm in real code?
Almost never. The library sorts are tested, optimised and correct for edge cases. Writing selection or insertion sort yourself is valuable for learning and for interviews, but in production code pass a Comparator to List.sort or Arrays.sort.
Java Exercises
Answer each one and check it instantly. If you get stuck, open the hint before the answer.
What is finalized after each selection-sort pass?
Why does insertion sort save value before shifting?
Java Quiz
2 questions to check what you learned.
What does LibrarySortDemo preserve?
- The original array order
- No duplicated values
- Every object through deep cloning
Why prefer Integer.compare to subtraction in a comparator?
- Subtraction can overflow
- Comparators forbid integers
- It automatically removes ties