Home | Tutorials | Articles | Videos | Products | Tools | Search
 Interviews | Open Source | Tag Cloud | Follow Us | Bookmark | Contact
 Data Structures > Sort > Shell Sort

# Shell Sort

The following example shows shell sort implementation.

• Best case time complexity of shell sort is O(n)
• Worst case time complexity of shell sort is O(n log2n)
• Average case time complexity of shell sort is O(n log2n)

 File Name  : com/bethecoder/tutorials/ds/sort/ShellSort.java Author  : Sudhakar KV Email  : [email protected]

 ``` package com.bethecoder.tutorials.ds.sort; import java.util.Arrays; public class ShellSort {   /**    * @param args    */   public static void main(String[] args) {     int[] list = { 112, 23, 376, 6, 5, 1, 8, 3, 9, 4, 0, 2, 7, 11, 26, 12, 19, 27, 86, 19 };     System.out.println("Before sort : " + Arrays.toString(list));     double timeTaken = shellSortTimeTaken(list);     System.out.println("After sort : " + Arrays.toString(list));     System.out.println("Time taken for ShellSort : " + timeTaken + " milliseconds.");   }   public static void shellSort(int [] list) {     int h = 1;     while((h*3+1) < list.length) {       h = h*3+1;     }     while (h > 0) {       for (int colIndex = h-1; colIndex < list.length; colIndex++) {         int val = list[colIndex];         int j = colIndex;                  //Sort column wise         while (j>=h && list[j-h]> val) {           list[j] = list[j-h];           j = j-h;         }                  list[j] = val;       }       h = h/3;     }   }      /**    * Sorts and returns the time taken in milliseconds.    *     * @param list    * @return    */   public static double shellSortTimeTaken(int[] list) {     long startTime = System.nanoTime();     shellSort(list);     long timeTaken = System.nanoTime() - startTime;     return timeTaken * Math.pow(10, -6);   } }```

It gives the following output,
```Before sort : [112, 23, 376, 6, 5, 1, 8, 3, 9, 4, 0, 2, 7, 11, 26, 12, 19, 27, 86, 19]
After sort : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 19, 19, 23, 26, 27, 86, 112, 376]
Time taken for ShellSort : 0.007821999999999999 milliseconds.
```

 Tweet Print