Inversion Lookahead in Sorted Concatenation
Suppose that and
b
=
(
b
1
,
…
,
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
∈
[
i
…
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
<
…
<
a
n
, therefore for each
k
∈
[
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
,
…
,
a
n
)
and
b
=
(
b
1
,
…
,
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
∈
[
j
…
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
≤
b
j
, since
b
is sorted in ascending order then we know that
a
i
≤
b
j
≤
b
j
+
1
≤
…
≤
b
m
, and thus for every
k
∈
[
j
…
m
]
we know
a
i
and
b
k
do not form an inversion.