Difficulty: Intermediate | Prerequisites: Inheritance and interfaces, basic array manipulation
Once you understand how interfaces and polymorphism work, the next question is: how do you put objects in order? Java's Comparable interface gives every class a standard way to define its own ordering, and sorting algorithms are the machinery that uses that ordering to arrange collections. This section also introduces recursion, a technique where a method calls itself, which underpins more advanced algorithms you will meet later in the course. You should be comfortable with inheritance, interfaces, and the implements keyword before starting here.
The Comparable interface requires a single compareTo method that returns a negative, zero, or positive integer to define ordering. Selection sort, bubble sort, and insertion sort are three elementary approaches to arranging elements. Recursion is a method calling itself with a simpler version of the problem until it hits a base case.
Comparable (interface)
A built-in Java interface with a single method, compareTo. Any class that implements Comparable is promising it knows how to rank its objects relative to one another. Think of it as a class saying, "I know how to sort myself."
compareTo method
The method defined by Comparable. Given two objects A and B, A.compareTo(B) returns a negative value if A comes before B, a positive value if A comes after B, and zero if they are considered equal in the ordering.
Delegation trick (compareTo)
When your object's fields are themselves comparable (such as Strings), you can delegate the comparison to their own compareTo instead of writing manual logic. For example, return name.compareTo(other.getName()); sorts by name alphabetically.
toString trick (compareTo)
If your object's toString() representation naturally reflects the ordering you want (e.g. dates formatted as "09/19"), you can delegate: return toString().compareTo(other.toString());.
Selection sort
A sorting algorithm that repeatedly finds the smallest unsorted element and moves it to the front of the sorted portion. In simple terms, it scans for the minimum, places it, then repeats.
Bubble sort
A sorting algorithm that makes repeated passes through the list, swapping adjacent elements if they are in the wrong order. The largest unsorted value "bubbles" to the end on each pass.
Insertion sort
A sorting algorithm that takes each element in turn and shifts it into its correct position within the already-sorted portion of the array. Think of it as sorting a hand of cards one card at a time.
Recursion
A technique where a method calls itself, each time with a smaller or simpler version of the original problem, until it reaches a base case that can be answered directly. In simple terms, the method "goes back into itself."
Comparable is a standard Java interface found in java.lang.
It contains exactly one method: compareTo.
To make a class sortable, declare it as implementing Comparable:
public class Employee implements ComparableThe return-value contract for A.compareTo(B):
Negative integer: A comes before B
Zero: A and B are considered equal in this ordering
Positive integer: A comes after B
For ascending order, use this - other (or the equivalent comparison).
For descending order, reverse it: other - this.
This pattern applies when comparing numeric fields. For non-numeric fields, use delegation.
If a field is already comparable (String, Integer, Date, etc.), delegate to its compareTo rather than writing your own logic:
// Sort employees alphabetically by namepublic int compareTo(Employee other) { return name.compareTo(other.getName());}
If your toString() output happens to sort correctly as a string (e.g. zero-padded dates like "09/19"), you can delegate to it:
// Sort Date objects by their string representationpublic int compareTo(Date other) { return toString().compareTo(other.toString());}
Scan the entire unsorted portion of the array to find the smallest element.
Swap it with the first unsorted position.
Move the boundary of the sorted portion one step to the right.
Repeat until the whole array is sorted.
Walk through the array comparing adjacent pairs.
If a pair is out of order, swap them.
After each full pass, the largest unsorted element has "bubbled" to its final position.
Repeat passes until no swaps occur.
Start from the second element (index 1). The single element at index 0 is trivially sorted.
Take the current element and compare it backwards against the sorted portion.
Shift larger elements one position to the right to make room.
Place the current element in its correct position.
Code walkthrough:
public static void insertionSort(int[] nums) { for (int i = 1; i < nums.length; i++) { int num = nums[i]; int index = i; while (index > 0 && num < nums[index - 1]) { nums[index] = nums[index - 1]; index--; } nums[index] = num; }}
The outer loop picks each unsorted element. The inner while loop shifts elements rightward until the correct insertion point is found.
Recursion is a method calling itself.
Every recursive method needs a base case (a condition that stops the recursion) and a recursive case (where the method calls itself with a smaller problem).
Without a base case, the method calls itself infinitely and causes a stack overflow.
compareTo return-value table:
| Meaning |
|---|---|
Negative (< 0) | A comes before B |
Zero (0) | A and B are equal in this ordering |
Positive (> 0) | A comes after B |
Ascending vs descending shortcut (numeric fields):
Desired order | Expression |
|---|---|
Ascending |
|
Descending |
|
Sorting is everywhere: search results ranked by relevance, spreadsheets ordered by column, leaderboards sorted by score. The Comparable interface is the reason Java's Collections.sort() and Arrays.sort() can sort objects of any type, provided the type defines its own ordering. Recursion powers algorithms like merge sort, quicksort, and tree traversals, which you will encounter in data structures courses.
Students often confuse the return-value direction. For ascending order, this - other is correct. Swapping the operands reverses the sort.
Students sometimes try to instantiate an interface directly (e.g. Comparable c = new Comparable()). Interfaces cannot be instantiated. You implement them in a concrete class.
Students forget that compareTo must return an int, not a boolean. It is not the same as equals.
With insertion sort, students sometimes think the inner loop is searching for the minimum. It is not. It is shifting elements to open up the correct slot for the current element.
⚠️ Expect to write a compareTo method from scratch given a class and a desired ordering. Know the implements Comparable declaration.
⚠️ Be ready to trace through insertion sort by hand on a short array. Know what the array looks like after each pass.
⚠️ Understand the delegation trick: when a field is already comparable, you do not reinvent the comparison.
⚠️ Know that compareTo returns negative, zero, or positive, not just -1, 0, or 1.
True or False: The Comparable interface contains multiple methods. False. It contains exactly one: compareTo.
Fill in the blank: For ascending order on a numeric field, the compareTo body typically returns this.field ______ other.field. - (minus)
True or False: Selection sort works by shifting each element into its correct position in a sorted sub-array. False. That describes insertion sort. Selection sort finds the minimum and swaps it to the front.
True or False: A recursive method without a base case will run forever (until it crashes). True. It causes a stack overflow.
Fill in the blank: To make a class sortable in Java, it should implement the ________ interface. Comparable
Q: Write the class declaration line for a Student class that can be sorted using compareTo.
A: public class Student implements Comparable
Q: What does A.compareTo(B) returning a negative number mean?
A: A comes before B in the defined ordering.
Q: Describe the delegation trick for compareTo and give an example.
A: If one of your object's fields is already a comparable type (like String), you delegate the comparison to that field's own compareTo. For example, to sort employees by name: return this.name.compareTo(other.getName());.
Q: What distinguishes insertion sort from selection sort?
A: Selection sort scans the unsorted portion for the minimum and swaps it into place. Insertion sort takes the next unsorted element and shifts it into its correct position within the already-sorted portion.
Q: What two components must every recursive method have?
A: A base case (stopping condition) and a recursive case (the method calling itself with a simpler input).
The Comparable interface ties directly back to interfaces and polymorphism: Arrays.sort() works on any Comparable type, which is polymorphism in action. Recursion connects forward to divide-and-conquer algorithms (merge sort, quicksort) and tree/graph traversals that you will study in data structures. Understanding these elementary sorts also gives you the baseline for appreciating why O(n log n) algorithms are a significant improvement.
Comparable interface, compareTo method, Java sorting, selection sort, bubble sort, insertion sort, ascending order, descending order, delegation trick, toString trick, recursion, base case, recursive case, stack overflow, Arrays.sort, Collections.sort, natural ordering, implements Comparable, sorting algorithms, CSCE, Texas A&M, intro to CS