Brief idea about Sorting

Five basic kinds of sorting algorithms are available to the programmer:

• Insertion sorts


• Exchange sorts


• Selection sorts


• Merge sorts


• Distribution sorts

An easy way to visualize how each sorting algorithm works is to think about how to sort a shuffled deck of cards lying on the table using each method. The cards are to be sorted by suit (clubs, diamonds, hearts, and spades) as well as by rank (2 through ace). You might have seen some of these algorithms in action at your last bridge game.

In an insertion sort, you pick up the cards one at a time, starting with the top card in the pile, and insert them into the correct position in your hand. When you have picked up all the cards, they are sorted.

In an exchange sort, you pick up the top two cards. If the one on the left belongs after the one on the right, you exchange the two cards’ positions. Then you pick up the next card and perform the compare on the two rightmost cards and (if needed) exchange their positions. You repeat the process until all the cards are in your hand. If you didn’t have to exchange any cards, the deck is sorted. Otherwise, you put down the deck and repeat the entire procedure until the deck is sorted.

In a selection sort, you search the deck for the lowest card and pick it up. You repeat the process until you are holding all the cards.

To perform a merge sort, you deal the deck into 52 piles of one card each. Because each pile is ordered (remember, there’s only one card in it), if you merge adjacent piles, keeping cards in order, you will have 26 ordered piles of 2 cards each. You repeat so that you have 13 piles of 4 cards, then 7 piles (6 piles of 8 cards and 1 pile of 4 cards), until you have 1 pile of 52 cards.

In a distribution (or radix) sort, you deal the cards into 13 piles, placing each rank on its own pile. You then pick up all the piles in order and deal the cards into 4 piles, placing each suit on its own pile. You put the four piles together, and the deck is sorted.

There are several terms you should be aware of when examining sorting algorithms. The first is natural. A sort is said to be natural if it works faster (does less work) on data that is already sorted, and works slower (does more work) on data that is more mixed up. It is important to know whether a sort is natural if the data you’re working with is already close to being sorted.

A sort is said to be stable if it preserves the ordering of data that are considered equal by the algorithm. Consider the following list:

Mary Jones
Mary Smith
Tom Jones
Susie Queue

If this list is sorted by last name using a stable sort, “Mary Jones” will remain before “Tom Jones” in the sorted list because they have the same last name. A stable sort can be used to sort data on a primary and secondary key, such as first and last names (in other words, sorted primarily by last name, but sorted by first name for entries with the same last name). This action is accomplished by sorting first on the secondary key, then on the primary key with a stable sort.

A sort that operates on data kept entirely in RAM is an internal sort. If a sort operates on data on disk, tape, or other secondary storage, it is called an external sort.