HeapSort is a comparison-based sorting algorithm that uses a data structure called a heap. It first transforms the input array into a max-heap, where the largest element is at the root. This allows the algorithm to efficiently remove the largest element and place it at the end of the array, reducing the size of the heap with each iteration. After building the max-heap, HeapSort repeatedly extracts the maximum element and rebuilds the heap until all elements are sorted. The overall time complexity of HeapSort is O(n log n), making it efficient for large datasets.