`O(|xs| + |ys|)`

. Merge arrays `xs`

and `ys`

. If the arrays are sorted according to `lt`

, then the
result is sorted as well. If two (or more) elements are equal according to `lt`

, they are preserved.

## Equations

- Array.merge lt xs ys = Array.merge.go lt xs ys (Array.mkEmpty (xs.size + ys.size)) 0 0

## Instances For

`O(|xs| + |ys|)`

. Merge arrays `xs`

and `ys`

. If the arrays are sorted according to `lt`

, then the
result is sorted as well. If two (or more) elements are equal according to `lt`

, they are preserved.

## Equations

- xs.mergeSortedPreservingDuplicates ys = Array.merge (fun (x x_1 : α) => (compare x x_1).isLT) xs ys

## Instances For

`O(|xs| + |ys|)`

. Merge arrays `xs`

and `ys`

, which must be sorted according to `compare`

and must
not contain duplicates. Equal elements are merged using `merge`

. If `merge`

respects the order
(i.e. for all `x`

, `y`

, `y'`

, `z`

, if `x < y < z`

and `x < y' < z`

then `x < merge y y' < z`

)
then the resulting array is again sorted.

## Equations

- xs.mergeDedupWith ys merge = Array.mergeDedupWith.go xs ys merge (Array.mkEmpty (xs.size + ys.size)) 0 0

## Instances For

**Alias** of `Array.mergeDedupWith`

.

`O(|xs| + |ys|)`

. Merge arrays `xs`

and `ys`

, which must be sorted according to `compare`

and must
not contain duplicates. Equal elements are merged using `merge`

. If `merge`

respects the order
(i.e. for all `x`

, `y`

, `y'`

, `z`

, if `x < y < z`

and `x < y' < z`

then `x < merge y y' < z`

)
then the resulting array is again sorted.

## Instances For

`O(|xs| + |ys|)`

. Merge arrays `xs`

and `ys`

, which must be sorted according to `compare`

and must
not contain duplicates. If an element appears in both `xs`

and `ys`

, only one copy is kept.

## Equations

- xs.mergeDedup ys = xs.mergeDedupWith ys fun (x x_1 : α) => x

## Instances For

**Alias** of `Array.mergeDedup`

.

`O(|xs| + |ys|)`

. Merge arrays `xs`

and `ys`

, which must be sorted according to `compare`

and must
not contain duplicates. If an element appears in both `xs`

and `ys`

, only one copy is kept.

## Instances For

`O(|xs| * |ys|)`

. Merge `xs`

and `ys`

, which do not need to be sorted. Elements which occur in
both `xs`

and `ys`

are only added once. If `xs`

and `ys`

do not contain duplicates, then neither
does the result.

## Equations

- xs.mergeUnsortedDedup ys = if xs.size < ys.size then Array.mergeUnsortedDedup.go ys xs else Array.mergeUnsortedDedup.go xs ys

## Instances For

Auxiliary definition for `mergeUnsortedDedup`

.

## Equations

- Array.mergeUnsortedDedup.go xs ys = let xsSize := xs.size; Array.foldl (fun (xs : Array α) (y : α) => if xs.any (fun (x : α) => x == y) 0 xsSize = true then xs else xs.push y) xs ys 0

## Instances For

**Alias** of `Array.mergeUnsortedDedup`

.

`O(|xs| * |ys|)`

. Merge `xs`

and `ys`

, which do not need to be sorted. Elements which occur in
both `xs`

and `ys`

are only added once. If `xs`

and `ys`

do not contain duplicates, then neither
does the result.

## Instances For

`O(|xs|)`

. Replace each run `[x₁, ⋯, xₙ]`

of equal elements in `xs`

with
`f ⋯ (f (f x₁ x₂) x₃) ⋯ xₙ`

.

## Equations

- Array.mergeAdjacentDups f xs = if h : 0 < xs.size then Array.mergeAdjacentDups.go f xs (Array.mkEmpty xs.size) 1 (xs.get ⟨0, h⟩) else xs

## Instances For

Auxiliary definition for `mergeAdjacentDups`

.

## Equations

- One or more equations did not get rendered due to their size.

## Instances For

**Alias** of `Array.mergeAdjacentDups`

.

`O(|xs|)`

. Replace each run `[x₁, ⋯, xₙ]`

of equal elements in `xs`

with
`f ⋯ (f (f x₁ x₂) x₃) ⋯ xₙ`

.

## Instances For

`O(|xs|)`

. Deduplicate a sorted array. The array must be sorted with to an order which agrees with
`==`

, i.e. whenever `x == y`

then `compare x y == .eq`

.

## Equations

- xs.dedupSorted = Array.mergeAdjacentDups (fun (x x_1 : α) => x) xs

## Instances For

**Alias** of `Array.dedupSorted`

.

`O(|xs|)`

. Deduplicate a sorted array. The array must be sorted with to an order which agrees with
`==`

, i.e. whenever `x == y`

then `compare x y == .eq`

.

## Equations

## Instances For

**Alias** of `Array.sortDedup`

.

`O(|xs| log |xs|)`

. Sort and deduplicate an array.