Unlike the mergesort and quicksort, heapsort doesn’t require massive recursion or multiple arrays to work and the time complexity of heapsort is O(n log(n)) . It utilizes a special data structure called heap. Before we take a look at the Heap sort algorithm, let’s explain the the (binary) heap data structure.