**
**

**A lower bound for simple sorting algorithms **
Simple sorting algorithms swap elements that
are not ordered.

Swapping is done by bubble sort, and by insertion sort.

Thus the complexity depends on the number of swaps.

To estimate how many swaps are needed on average, we define **inversion **in the following way:

**Definition:** An **inversion** is an
ordered pair (A_{i}, A_{j}) such that i < j
but A_{i} > A_{j}.

**Example:** 10, 6, 7, 15, 3, 1

Inversions are:

( 10, 6 ), ( 10, 7 ), ( 10, 3 ), ( 10, 1 )

( 6, 3 ), ( 6, 1 )

( 7, 3 ), ( 7, 1 )

( 15, 3 ), ( 15, 1 )

( 3, 1 )

The following is true:

- Swapping adjacent elements that are out of order removes one inversion.
- A sorted array has no inversions.
- Sorting an array that contains
*i* inversions
requires at least *i* swaps of adjacent elements.

How many inversions are there in an average unsorted array?

In general this is a tricky question to answer - just
what is meant by average?

However, we can make a couple
of simplifying assumptions:

- There are no duplicates in the list.
- Since the elements are unique (by assumption),
all that matters is their relative rank.

Accordingly we identify them with the first N integers
{1, 2, ..., N}

and assume the elements we have to sort are the first N integers.

Under these circumstances we can say the following:

**Theorem 1** *[Average number of inversions] *

The average number of inversions in an array of N
distinct elements is **N (N - 1) / 4**

**Proof:**

Given an array A, consider A_{r}, which
is the array in reverse order.

Now consider a pair (x, y)
with x < y.

This pair is an inversion in
exactly one of A, A_{r}.

The total
number of such pairs is given by N (N - 1)/2,

and (on average) half of these will be inversions in A.
Thus A has N (N - 1) / 4 inversions.

Consequently the insertion sort has an average running time
of O(N^{2}).

In fact we can generalize this result to all sorting algorithms

that work by exchanging adjacent elements to eliminate inversions.

**Theorem 2** Any algorithm that sorts by exchanging
adjacent elements requires Ω (N^{2})
time on average.

The proof follows immediately from the fact that the average
number of

inversions is N(N-1)/4: each adjacent swap
removes only one inversion,

so
Ω(N^{2})
swaps are required.

Theorem 2 above implies that for a sorting algorithm to run
in less than quadratic time

it must do something other than swap adjacent elements.