Insertion Sort

The algorithm that people often use to sort bridge hands is to consider the cards one at a time, inserting each into its proper place among those already considered (keeping them sorted). In a computer implementation, we need to make space to insert the current item by moving larger items one position to the right, before inserting the current item into the vacated position. A

As in selection sort, the items to the left of the current index are in sorted order during the sort, but they are not in their final position, as they may have to be moved to make room for smaller items encountered later. The array is, however, fully sorted when the index reaches the right end.

Unlike that of selection sort, the running time of insertion sort depends on the initial order of the items in the input. For example, if the array is large and its entries are already in order (or nearly in order), then insertion sort is much, much faster than if the entries are randomly ordered or in reverse order.

Insertion sort works well for certain types of nonrandom arrays that often arise in practice, even if they are huge. For example, as just mentioned, consider what happens when you use insertion sort on an array that is already sorted. Each item is immediately determined to be in its proper place in the array, and the total running time is linear.

(The running time of selection sort is quadratic for such an array.) The same is true for arrays whose keys are all equal.

You may also Like

Merge Sort

Merge Sort

December 31, 2020
Bubble Sort

Bubble Sort

December 31, 2020
Quick Sort

Quick Sort

December 31, 2020

Leave a reply

Your email address will not be published. Required fields are marked *

About Me

I am a dad of two wonderful boys, Utku Efe and Omer Eren, and married with Elif. In addition, I am an academician and AI/ML scientist because I worked more than 15 years in universities, have M.S and Ph.D. thesis and more than 20 scientific papers/presentations and 100 citations. Now people call me as a Principal Developer in my last company :).
I am really hungry on learning new technologies and get more fun while developing new softwares.

Stay Connected

×