Partition the array into a sorted part and an unsorted part. Structure the unsorted part like a heap. Think about the storage changes that need to occur after
.
.