**Sorting Algorithm Tutorials - Herong's Tutorial Examples** - Version 6.01, by Dr. Herong Yang

Insertion Sort - Performance

This section provides a tutorial on how to measure the performance of the Insertion Sort algorithm. My first Java implementation of Insert Sort is performing at the O(N*N) order level.

Now let's see how my Java implementation of the Insertion Sort algorithm performs. I tried this implementation with my SortTest.java under JDK 1.3.1. Here are the results:

Array size: 1000 Average sorting time: 21 milliseconds Number of tests: 1000 Performance: 21.0 O(N) nanoseconds Performance: 2.1072099696478683 O(N*Log2(N)) nanoseconds Performance: 0.021 O(N*N) nanoseconds Array size: 2000 Average sorting time: 83 milliseconds Number of tests: 1000 Performance: 41.5 O(N) nanoseconds Performance: 3.784499031049363 O(N*Log2(N)) nanoseconds Performance: 0.02075 O(N*N) nanoseconds Array size: 3000 Average sorting time: 191 milliseconds Number of tests: 1000 Performance: 63.666666666666664 O(N) nanoseconds Performance: 5.511909130172683 O(N*Log2(N)) nanoseconds Performance: 0.021222222222222222 O(N*N) nanoseconds

The results showed us that the performance of insertion method is O(N*N), because the last performance line gave me a constant, when I increased the array size.

I also executed my SortTest.java with java.util.Arrays.sort():

Array size: 10000 Average sorting time: 17 milliseconds Number of tests: 1000 Performance: 1.7 O(N) nanoseconds Performance: 0.127937748157192 O(N*Log2(N)) nanoseconds Performance: 1.7E-4 O(N*N) nanoseconds Array size: 20000 Average sorting time: 45 milliseconds Number of tests: 1000 Performance: 2.25 O(N) nanoseconds Performance: 0.1574779740961549 O(N*Log2(N)) nanoseconds Performance: 1.125E-4 O(N*N) nanoseconds Array size: 30000 Average sorting time: 70 milliseconds Number of tests: 1000 Performance: 2.3333333333333335 O(N) nanoseconds Performance: 0.15688726823636978 O(N*Log2(N)) nanoseconds Performance: 7.777777777777778E-5 O(N*N) nanoseconds

The results was very impressive. I had to increase the array size to 10000 to get the performance measurements. As you can see, the performance is at the order of O(N*Log2(N)).

*Last update: 2011.*

Table of Contents

Introduction of Sorting Algorithms

Java API for Sorting Algorithms

►Insertion Sort Algorithm and Implementation

Insertion Sort - Algorithm Introduction

Insertion Sort - Java Implementation

Insertion Sort - Implementation Improvements

Selection Sort Algorithm and Implementation

Bubble Sort Algorithm and Implementation

Quicksort Algorithm and Implementation

Merge Sort Algorithm and Implementation

Heap Sort Algorithm and Implementation

Shell Sort Algorithm and Implementation