interval partitioning

Inversion Lookahead in Sorted Concatenation

Suppose that

a = (a_{1}, \dots, a_{n})

and

b = (b_{1}, \dots, b_{m})

are finite tuples sorted in ascending order and define

c = concat (a, b)

. If

a_{i}

and

b_{j}

form an inversion then for every

k \in [i \dots n]

a_{k}

and

b_{j}

form an inversion in

c

Before the proof starts note that $c$ has $n + m$ elements, and then $b_{j}$ refers to the element at position $n + j$ with respect to $c$

We know that $b_{j} < a_{i}$ because they form an inversion, we also know that $a$ is sorted in ascending order, therefore we know that $b_{j} < a_{i} < a_{i + 1} < \dots < a_{n}$ , therefore for each $k \in [i . . . n]$ we know $(k, n + j)$ forms an inversion in $c$ as needed.

No Inversion Lookahead in Sorted Concatenation

Suppose that

a = (a_{1}, \dots, a_{n})

and

b = (b_{1}, \dots, b_{m})

are finite tuples sorted in ascending order and define

c = concat (a, b)

. If

a_{i}

and

b_{j}

do not form an inversion then for every

k \in [j \dots m]

a_{i}

and

b_{k}

do not form an inversion in

c

Since

a_{i}

and

b_{j}

do not form an inversion then we know that

a_{i} \leq b_{j}

, since

b

is sorted in ascending order then we know that

a_{i} \leq b_{j} \leq b_{j + 1} \leq \dots \leq b_{m}

, and thus for every

k \in [j \dots m]

we know

a_{i}

and

b_{k}

do not form an inversion.

counting_inversions

is Correct

Given any list

A

counting_inversions

returns the number of inversions in

A

🏗️ ΘρϵηΠατπ🚧 (under construction)

🏗️ $Θ ρ ϵ η Π α τ π$ 🚧 (under construction)