Java Reference
In-Depth Information
5. The merge sort algorithm sorts an array by cutting the array in half, recursively
sorting each half, and then merging the sorted halves.
6. Merge sort is an O(n log(n)) algorithm. The n log(n) function grows much more
slowly than n
2
.
7. The
Arrays
class implements a sorting method that you should use for your
Java programs.
8. A linear search examines all values in an array until it finds a match or reaches
the end.
9. A linear search locates a value in an array in O(n) steps.
10. A binary search locates a value in a sorted array by determining whether the
value occurs in the first or second half, then repeating the search in one of the
halves.
11. A binary search locates a value in an array in O(log(n)) steps.
12. The
sort
method of the
Arrays
class sorts objects of classes that implement
the
Comparable
interface.
13. The
Collections
class contains a
sort
method that can sort array lists.
FURTHER READING
1. Michael T. Goodrich and Roberto Tamassia, Data Structures and
Algorithms in Java, 3rd edition,John Wiley & Sons, 2003.
658
659
CLASSES, OBJECTS, AND METHODS INTRODUCED IN THIS
CHAPTER
java.lang.Comparable<T>
compareTo
java.lang.System
currentTimeMillis
java.util.Arrays
binarySearch
sort
