Chapter 6 - Sorting Machine using Heapsort

Document last modified:

Sorting_Machine can be implemented by the sorting algorithms listed in the table below.
The actual work done to get the items sorted will be performed in one of the three different sorting machine operations:
- Insert
- Extract
- Change_To_Extraction_Phase.
Here is a breakdown of where the work will be performed (based on the sorting algorithm chosen) and how much work is done.
Note the work is given in terms of Big-O performance, where N is the total number of items to be sorted.

Algorithm Used	Insert	Extract	Change_To_Extraction_Phase
Insertion Sort	O(N²) N items inserted O(N) per item	O(1)	O(1)
Selection Sort	O(1)	O(N²) N items extracted O(N) per item	O(1)
Exchange Sort	O(1)	O(1)	O(N²)
Quick Sort	O(1)	O(1)	O(N²) worst, O(N * Log₂ N) best
Merge Sort	O(1)	O(1)	O(N * Log₂ N)
Heap Sort	O(1)	O(N * Log₂ N) for N items extracted O( Log₂ N) for 1 item extracted	O(N)

Heap Sort:

Insert	takes item to be sorted and adds it to the rightmost free location in the array, this increases the heap's size by 1
Change_To_Extraction_Phase	call Build_Heap to build the heap
Extract	remove extreme item from location 1 of the array, move item in last location of the heap to location 1 and then call Heapify this decreases the heap's size by 1
Size	returns the number of items currently in the heap, not the array size