Java Reference
In-Depth Information
Chapter
9
Faster Sorting
Methods
Contents
Merge Sort
Merging Arrays
Recursive Merge Sort
The Efficiency of Merge Sort
Iterative Merge Sort
Merge Sort in the Java Class Library
Quick Sort
The Efficiency of Quick Sort
Creating the Partition
Java Code for Quick Sort
Quick Sort in the Java Class Library
Radix Sort
Pseudocode for Radix Sort
The Efficiency of Radix Sort
Comparing the Algorithms
Prerequisites
Chapter
4
The Efficiency of Algorithms
Chapter
7
Recursion
Chapter
8
An Introduction to Sorting
Objectives
After studying this chapter, you should be able to
•
Sort an array into ascending order by using the following methods: merge sort, quick sort, and radix sort
•
Assess the efficiency of a sort and discuss the relative efficiencies of the various methods
T
he sorting methods that you saw in the previous chapter often are sufficient when
you want to sort small arrays. They even can be a reasonable choice if you need to sort a
larger array once. Additionally, the insertion sort is a good way to sort a chain of linked
nodes. However, when you need to sort very large arrays frequently, those methods take
