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.

Heap sort:

Heapsort (method) is a comparison-based sorting algorithm, and is part of the selection sort family. Although somewhat slower in practice on most machines than a good implementation of quicksort, it has the advantage of a worst-case Θ(n log n) runtime. Heapsort is an in-place algorithm, but is not a stable sort.

Worest case performance O(n log n)

Best case performance O(n log n)

Average case performance O(n log n)

Advantages of heap sort:

 1.It is efficient for sorting large number of elements.

 2.It has the advantages of worst case O(N log N) running time.
 
Limitations:

  1. It is not a stable sort.

  2. It requires more processing time

Alogrithm steps:

Step1: Read the size of the list

Step2: Read the elements of the list

Step3: Binary heap construction.

             1) Structrue Property:

                     For any element in array position I,the left child is in position 2i,the right child is in 2i+1,(ie) the cell after the left child.

             2) Heap Order Property:

                    The value in the parent node is smaller than or equal to the key value of  any of its child node.Build the heap,apply the heap order propery starting from the right. most non-leaf node at the bottom level.

Step 4: Delete min routine is performed.

      The array elements aer stored using deletemin operation,which gives the elements arranged in descending order.