# Heapsort

## Introduction

Heapsort is a comparison-based sorting algorithm that uses a binary heap data structure. It was first proposed by J. W. J. Williams in 1964. Heapsort is an in-place algorithm, meaning that it sorts the array in place, without needing any additional memory. It has a time complexity of O(n log n), which makes it efficient for large data sets.

## Implementation

Here is an implementation of heapsort in OCaml:

```
let swap arr i j =
let temp = arr.(i) in
arr.(i) <- arr.(j);
arr.(j) <- temp
let rec heapify arr n i =
let largest = ref i in
let left = 2 * i + 1 in
let right = 2 * i + 2 in
if left < n && arr.(left) > arr.(!largest) then
largest := left;
if right < n && arr.(right) > arr.(!largest) then
largest := right;
if !largest <> i then (
swap arr i !largest;
heapify arr n !largest
)
let heapsort arr =
let n = Array.length arr in
for i = n / 2 - 1 downto 0 do
heapify arr n i
done;
for i = n - 1 downto 1 do
swap arr 0 i;
heapify arr i 0
done
```

Here is an example of how to use the heapsort function:

```
let arr = [|4; 2; 7; 1; 3|]
let () = heapsort arr
let () = Array.iter (Printf.printf "%d ") arr
```

Output:

```
1 2 3 4 7
```

## Step-by-step Explanation

- Build a max heap from the input data. A binary heap is a complete binary tree where each node is greater than or equal to its children. The largest element is stored at the root of the heap.
- Swap the root node with the last element in the array. Decrease the heap size by 1.
- Call heapify on the root node to restore the heap property.
- Repeat steps 2-3 until the heap size is 1.

The heapify function takes three arguments: the array to be sorted, the size of the heap, and the index of the current node. It compares the current node with its left and right children and swaps it with the largest child if necessary. It then recursively calls heapify on the largest child to ensure that the subtree rooted at the current node is also a heap.

## Complexity Analysis

The time complexity of heapsort is O(n log n) in the worst case. Building the heap takes O(n) time, and each call to heapify takes O(log n) time. We call heapify n-1 times in the second loop, so the total time complexity is O(n log n).

Heapsort is an in-place sorting algorithm, so it requires no additional memory beyond the array to be sorted. However, it is not a stable sorting algorithm, meaning that it does not preserve the relative order of equal elements in the input array.