Java 9 Data Structures and Algorithms

Chapter 6. Efficient Sorting – quicksort and mergesort

In the last chapter, we explored a few simple sorting algorithms. The problem with those is that they are not efficient enough. In this chapter, we will cover two efficient sorting algorithms and we will also see how they are efficient.

In this chapter, you will learn the following topics:

• quicksort
• mergesort
• Optimality of efficiency in sorting algorithms

quicksort

We want to develop an algorithm that sorts an array of elements efficiently. Our strategy will be simple; we will somehow try to divide the array into two halves in such a way that sorting each half will complete the sorting. If we can achieve this, we can recursively call the sorting algorithm this way. We already know that the number ...