Insertion Sort - Implementation Improvements

This section provides a tutorial on how to improve the performance of the Insertion Sort implementation by using binary search method.

One area to improve this implementation is the inner loop, where we sequentially comparing each element with the selected element by the outer loop. Since we are doing this in the sorted section of the collection, we could replace this search by a binary search method.

Here is my improved implementation of insertion sort:

  /* HyArrays.java
 * This class contains sorting methods similar to java.util.Arrays.sort().
 * All sorting methods should have a signiture of
 * %Sort(Object[] a, int fromIndex, int toIndex)
 * where "fromIndex" is inclusive, and "toIndex" is exclusive.
 * Copyright (c) HerongYang.com. All Rights Reserved.
 */
public class HyArrays {
   public static void insertionSortImproved(HyObject[] a, int fromIndex,
      int toIndex) {
      HyObject d;
      for (int i=fromIndex+1; i<toIndex; i++) {
         d = a[i];
         int jLeft = fromIndex;
         int jRight = i-1;
         if ((a[jRight]).compareTo(d)>0) {
            while (jRight-jLeft>=2) {
               int jMiddle = (jRight-jLeft)/2 + jLeft - 1;
               if ((a[jMiddle]).compareTo(d)>0) {
                  jRight = jMiddle;
               } else {
                  jLeft = jMiddle + 1;
               }
            }
            if (jRight-jLeft==1) {
               int jMiddle = jLeft;
               if ((a[jMiddle]).compareTo(d)>0) {
                  jRight = jMiddle;
               } else {
                  jLeft = jMiddle + 1;
               }
            }
            int j = i;
            for (j=i; j>jLeft; j--) {
               a[j] = a[j-1];
            }
            a[j] = d;
         }
      }
   }
}

Of course, it has more lines of code. But watch the improvement in performance:

Array size: 10000
Average sorting time: 55 milliseconds
Number of tests: 1000
Performance: 5.5 O(N) microseconds
Performance: 0.4139162440379741 O(N*Log2(N)) microseconds
Performance: 5.5E-4 O(N*N) microseconds

Array size: 20000
Average sorting time: 221 milliseconds
Number of tests: 1000
Performance: 11.05 O(N) microseconds
Performance: 0.7733918283388941 O(N*Log2(N)) microseconds
Performance: 5.525E-4 O(N*N) microseconds

Array size: 30000
Average sorting time: 500 milliseconds
Number of tests: 1000
Performance: 16.666666666666668 O(N) microseconds
Performance: 1.1206233445454983 O(N*Log2(N)) microseconds
Performance: 5.555555555555556E-4 O(N*N) microseconds

It is still at the order of O(N*N). But I have reduced the performance by 78% from 0.641 to 0.500 seconds on the array size of 30,000.

Question: Can you do better than this? If you can, please let me know.

As a reference, results from an older computer are listed below:

Array size: 1000
Average sorting time: 9 milliseconds
Number of tests: 1000
Performance: 9.0 O(N) microseconds
Performance: 0.9030899869919435 O(N*Log2(N)) microseconds
Performance: 0.0090 O(N*N) microseconds

Array size: 2000
Average sorting time: 34 milliseconds
Number of tests: 1000
Performance: 17.0 O(N) microseconds
Performance: 1.5502767115141969 O(N*Log2(N)) microseconds
Performance: 0.0085 O(N*N) microseconds

Array size: 3000
Average sorting time: 76 milliseconds
Number of tests: 1000
Performance: 25.333333333333332 O(N) microseconds
Performance: 2.193220386874994 O(N*Log2(N)) microseconds
Performance: 0.008444444444444444 O(N*N) microseconds

Table of Contents

 About This Book

 Introduction of Sorting Algorithms

 Java API for Sorting Algorithms

Insertion Sort Algorithm and Java Implementation

 Insertion Sort - Algorithm Introduction

 Insertion Sort - Java Implementation

 Insertion Sort - Performance

Insertion Sort - Implementation Improvements

 Selection Sort Algorithm and Java Implementation

 Bubble Sort Algorithm and Java Implementation

 Quicksort Algorithm and Java Implementation

 Merge Sort Algorithm and Java Implementation

 Heap Sort Algorithm and Java Implementation

 Shell Sort Algorithm and Java Implementation

 Sorting Algorithms Implementations in PHP

 Sorting Algorithms Implementations in Perl

 Sorting Algorithms Implementations in Python

 Performance Summary of All Implementations

 References

 Full Version in PDF/EPUB