# sortedArray

## 🌌sortedArray

sortedarray -- sorted one-dimensional immutable array

This takes an unsorted array and a compare function as an arguments and

returns a sorted one.

Non-mutating heap sort is used internally. This gives guaranteed peformance in

O(n log n) comparisons and assignments for an array of size n.

This is a little wasteful on allocated memory, which is also O(n log n) since

partially sorted arrays are thrown away. This might be improved to use an

in-place heap sort to bring allocated memory down to O(n).

find index of key for which cmp returns 0

The guaranteed performance is in O(log n) comparisons.

result is the index where cmp results in 0 or nil if no such index

was found in this array. In case several instance equal match,

the index of one matching key will be returned, but is not

specified which one.

find index of given key using binary search

The guaranteed performance is in O(log n) comparisons.

result is the index where key was found or nil if key is not

in this array. In case several instance equal to key are in

this sortedArray, the index of one of the matching keys will be

returned, but is not specified which one.

orginal, unsorted array

predicate defining total order on T.

must satisfy:

forAll a,b: lessOrEqual(a, b) <=> (a = b)

forAll a,b: lessOrEqual(a, b) || lessOrEqual(b, a)

forAll a,b,c: (lessOrEqual(a, b) && lessOrEqual(b, c)): lessOrEqual(a, c)

perform heap sort on the given array

result is a new array that is sorted