F-Sharp/Algorithms/Sort/Heap_Sort.fs at main · TheAlgorithms/F-Sharp · GitHub

30 lines (25 loc) · 879 Bytes

namespace Algorithms.Sort

module HeapSort =

let inline swap (a: 'T []) i j =

let temp = a.[i]

a.[i] <- a.[j]

a.[j] <- temp

let inline sift cmp (a: 'T []) start count =

let rec loop root child =

if root * 2 + 1 < count then

let p =

child < count

- 1

&& cmp a.[child] a.[child + 1] < 0

let child = if p then child + 1 else child

if cmp a.[root] a.[child] < 0 then

swap a root child

loop child (child * 2 + 1)

loop start (start * 2 + 1)

let inline heapsort cmp (a: 'T []) =

let n = a.Length

for start = n / 2 - 1 downto 0 do

sift cmp a start n

for term = n - 1 downto 1 do

swap a term 0

sift cmp a 0 term

Expand file tree