Sorting:

Sorting algorithm is an algorithm that puts elements of a list in a certain order . The most-used orders are numerical order and lexicographical order.

Sorting algorithm classification:

Computaional complexcity.

Memory utilization

Stability-Maintaining relative order of records with equal keys.

No.of comparisions

Methods applied like insertion,exchange,,selection,merging etc.

Sorting is a process of linear ordering of list of objects

Sorting techniques are categoried into:

1. Internal sorting

2. External sorting

Internal sorting:

It takes the place in the main memory of a computer.

                 Eg: Bubble sort,Insertion sort,Shell sort,Quick sort,Heap Sort,etc

External sorting:

It takes the place in secondary memory of a computer,Since the number of objects to be stored is too large to fit in main memory.

                Eg:Merge sort,Multiway Merge,Polyphase merge.

Shell sort:

Shell sort is a sorting algorithm that is a generalization of insertion sort, with two observations:

• insertion sort is efficient if the input is "almost sorted", and
• insertion sort is typically inefficient because it moves values just one position at a time.

Shellsort is one of the oldest sorting algorithms, named after its inventor D.L. Shell (1959) . It is fast, easy to understand and easy to implement. However, its complexity analysis is a little more sophisticated.

Analysis of the shell sort:

  Worest case performance O(n2)

  Best case performance O(n log n)

Average case performance O(n1.5)           

Advantages of shell sort:

1. It is one of the fastest algorithms for sorting small number of elements.

2. It requires relatively small amounts of memory.

Alogrithm steps:

 Step 1:

          The whole array is first fragmented into K segments, where K is preferably a prime number.

Step 2:

        Now the whole are is partially sorted.

Step 3:

          The value of K is reduced which increase the size of each segment and reduce the no of segments.

Step 4:

        The next value of K is chosen so that it is relatively prime to its previous value.

Step 5:

          Repeat the step 4 until K=1,at which the array is sorted.

         The insertion sort is applied in each segment, so each successive segment is partially sorted.