Algorithms For Dummies

Sorting Data Using Mergesort  

and Quicksort

Sorting is one of the essentials of working with data. Consequently, a lot of people 

have come up with a lot of different ways in which to sort data over the years. All 

these techniques result in ordered data, but some work better than others do, and 

some work exceptionally well for specific tasks. The following sections help you 

understand the need for searching as well as consider the various search options.

Defining why sorting data is important

A case can be made for not sorting data. After all, the data is still accessible, even 

if you don’t sort it — and sorting takes time. Of course, the problem with unsorted 

data is the same problem as that junk drawer in your kitchen (or wherever you 

have your junk drawer — assuming that you can find it at all). Looking for any-

thing in the junk drawer is time consuming because you can’t even begin to guess 

where to find something. Rather than just reach in and take what you want, you 

must take out myriad other items that you don’t want in an effort to find the one 

item you need. Unfortunately, the item you need might not be in the junk drawer 

in the first place—you might have thrown it out or put it in a different drawer.

The junk drawer in your home is just like unsorted data on your system. When the 

data is unsorted, you need to search one item at a time, and you don’t even know 

whether you’ll find what you need without searching every item in the dataset 

first. It’s a frustrating way to work with data. The binary search example in the 

“Considering  divide  and  conquer”  section  of  Chapter  5  points  out  the  need  for 

sorting quite well. Imagine trying to find an item in a list without sorting it first. 

Every search becomes a time-consuming sequential search.

---

CHAPTER 7