Table of contents
Overview
O(n²) Time Complexity in all cases.
Does less “Memory writes” when compared with other algorithms such as Quick sort, Merge sort, Insertion sort and Bubble sort.
However, not an optimal algorithm in terms of “Memory writes”. There is other algorithm called Cycle sort which is optimal in terms of memory writes.
Basic idea for Heap sort.
Not Stable (order of elements may change).
In-Place Algorithm
Idea
Iterate through loop
First iteration, find the minimum element and put it in the first place.
Second iteration, find the minimum element and put it in the second place.
Repeat this process, at the end the array is sorted.
Code
Time Complexity
The internal for-loop runs:
$$\begin{align*} (n-1) + (n-2) + \dots + 2 + 1 \\ = \frac{n(n-1)}{2} \\ \theta(n^2) \end{align*}$$