Today’s Material

• Sorting: Definitions
• Basic Sorting Algorithms
– BubleSort
– SelectionSort
– InsertionSort
• Divide & Conquer (Recursive) Sorting
Algorithms
– MergeSort

• Inversions Counting

• External Sorting 1
 Why Sort?
• Sorting algorithms are among the most frequently
used algorithms in computer science
– Crucial for efficient retrieval and processing of large
volumes of data, e.g., Database systems
– Typically a first step in some more complex algorithm
• An initial stage in organizing data for faster retrieval

• Allows binary search of an N-element array in

O(log N) time

• Allows O(1) time access to kth largest element in

the array for any k

• Allows easy detection of any duplicates

2
 Sorting – Things to consider
• Space: Does the sorting algorithm require extra
memory to sort the collection of items?
– Do you need to copy and temporarily store some subset of
the keys/data records?
– An algorithm which requires O(1) extra space is known as
an in place sorting algorithm

• Stability: Does it rearrange the order of input data

records which have the same key value
(duplicates)?
– E.g. Given: Phone book sorted by name. Now sort by
district – Is the list still sorted by name within each
county?
– Extremely important property for databases – next slide
– A stable sorting algorithm is one which does not
rearrange the order of duplicate keys 3
 Bubble Sort
/* Bubble sort pseudocode for integers
* A is an array containing N integers */
BubleSort(int A[], int N){
for(int i=0; i<N; i++) {
/* From start to the end of unsorted part */
for(int j=1; j<(N-i); j++) {
/* If adjacent items out of order, swap
*/
if( A[j-1] > A[j] ) SWAP(&A[j-1], &A[j]);
} //end-for-inner
} //end-for-outer
} //end-BubbleSort

N  1 N  i 1 N1
T ( N )   1  ( N  i  1) O( N 2
)
i 0 j 1 i 0 4
 Selection Sort
SelectionSort(int A[], int N){
for(int i=0; i<N; i++) {
int maxIndex = i; // max index
for(int j=i+1; j<N; j++) {
if (A[j] > A[maxIndex]) maxIndex = j;
} //end-for-inner
if (i != maxIndex) SWAP(&A[i], &A[maxIndex]);
} //end-for-outer
} //end-SelectionSort

N1 N1 N1

T ( N )   1  ( N  i  1) O( N 2
)
i 0 j i 1 i 0

5
 Insertion Sort
/* Insertion sort pseudocode for integers
A is an array containing N integers */
InsertionSort(int A[], int N){
int j, P, Tmp;
for(P = 1; P < N; P++ ) {
Tmp = A[ P ];
for(j = P; j > 0 && A[ j - 1 ] > Tmp; j-- ){
A[ j ] = A[ j - 1 ]; //Shift A[j-1] to right
} //end-for-inner
A[ j ] = Tmp; // Found a spot for A[P] (=
Tmp)
} //end-for-outer
} //end-InsertionSort

• In place (O(1) space for Tmp) and stable

• Running time:
• Worst case is reverse order input = O(N2)
• Best case is input already sorted = O(N). 6
Summary of Simple Sorting Algos
• Simple Sorting choices:
– Bubble Sort - O(N2)
– Selection Sort - O(N2)
– Insertion Sort - O(N2)

– Insertion sort gives the best practical

performance for small input sizes (~20)

7
 Recursive Sorting Algorithms
• What about a divide & conquer strategy?
• Merge Sort
– Divide the array into two halves
– Sort the left half
– Sort the right half
– Merge the sorted halves to obtain the final
sorted array

• Quick Sort
– Uses a different strategy to partition the array
into two halves

8
 MergeSort Example
0 1 2 3 4 5 6 7

8 2 9 4 5 3 1 6
Divide

Divide 8 2 9 4 5 3 1 6
8 2 9 4 5 3 1 6
Divide
1 element 8 2 9 4 5 3 1 6
Merge
2 8 4 9 3 5 1 6
Merge
2 4 8 9 1 3 5 6
Merge
Sorted Array 1 2 3 4 5 6 8 9

9
 MergeSort
• MergeSort – A[1..N]
• Stopping rule:
• If N == 1 then done
• Key Step
• Divide:
• Consider the smaller arrays A[1..N/2], A[N/2+1..N]
• Conquer:
• M1 = Sort (A[1..N/2])
• M2 = Sort (A[N/2+1..N]
• Merge:
• Merge(M1, M2) to produce the sorted array A

10
MergeSort PseudoCode

11
 Recursive Calls of MergeSort

N/2

N/4

N/8

T(n) = 2*T(n/2) + N

Time to sort the 2 Time to merge the 2

subarray sorted subarray 12
 Inversion Counting
• Let’s consider a variant on MergeSort
• Although the problem description is not
related, the solutions are closely related

• Suppose a group of people rank a set of

movies from the most popular to the least
• After people rank the movies, you want to
know which people tended to rank the
movies in the same way

13
 Ranking Example
Movie Ali Bulent Cem
Movie1 1 4 6
Movie2 2 1 8
Movie3 3 3 4
Movie4 4 2 1
Movie5 5 5 7
Movie6 6 7 2
Movie7 7 8 5
Movie8 8 6 3

• Given two such lists, we want to determine

their degree of similarity
– One possible definition for similarity is to count
the number of inversions
14
 Inversion: Definition
• Given two lists of preferences, L1 and L2,
define an inversion to be a pair of movies “x”
and “y” such that
– L1 has “x” before “y”, L2 has “y” before “x”
– Max (n 2) = n(n-1)/2 inversions
– If the two lists are the same, there are no inversions

Ali: 1 2 3 4 5 6 7 8 Ali: 1 2 3 4 5 6 7 8

Bulent: 4 1 3 2 5 7 8 6 Cem: 6 8 4 1 7 2 5 3

6 inversions 18 inversions
15
 Inversion Counting
• We can reduce the problem from one involving
two lists to one involving just one list as follows
– Assume L1 consists of the sequence <1, 2, 3, 4, .., n>
– Let the other list L2 be denoted by <a1, a2, .., an>
– Then, an inversion is a pair of indices (i, j) such that
i<j but ai > aj.
– Given a list of “n” distinct numbers, our objective is to
count the number of inversions

List1: 1 2 3 4 5 6 7 8

List2: 4 1 3 2 5 7 8 6 16
 Inversion Counting: Naïve
Solution
• We can easily solve this problem in O(n2) time
– For each ai, search all i+1<=j<=n, and increment
a counter for every j such that ai > aj

4 1 3 2 5 7 8 6

– Let’s trace:
• For 4: Number of inversions: 3 (4 is bigger than 1, 2 and 3)
• For 1: Number of inversions: 0
• For 3: Number of inversions: 1 (3 is bigger than 2)
• For 2: Number of inversions: 0
• For 5: Number of inversions: 0
• For 7: Number of inversions: 1 (7 is bigger than 6)
• For 8: Number of inversions: 1 (8 is bigger than 6)
• Total: 6 inversions
17
 Divide & Conquer Inversion
Counting
• We can design a more efficient divide &
conquer solution as follows:

• InversionCount(int A, int n){

if (n== 1) return 0; // no inversion
int left = InversionCount(A, n/2);
int right = InversionCount(&A[n/2], n/2);

int between = Count the number of inversions occurring

between
the two sequences;

return left + right + between;

} // end-InversionCount 18
 Divide & Conquer Inversion
Counting
• The key to an efficient implementation of the
algorithm is the step where we count the
number of inversions between the two lists
– It will be much easier if we sort the list as we
count the number of inversions
6 8 4 1 7 2 5 3

6 8 4 1 7 2 5 3
Sort & Count: 5 inversions Sort & Count: 4 inversions

1 4 6 8 2 3 5 7

# of inversions between the lists: 9

6 8 4 1 7 2 5 3
19
Total: 5 + 4 + 9 = 18 inversions
 Divide & Conquer Inversion (1)
• Assume the input is given as an array
A[p..r]
• We split into A[p..m], A[m+1..r], which are
sorted during the merging step
• During merging, maintain two indices “i”
and “j”, indicating the current elements of
the left & the right subarrays

20
Counting inversions when A[i] <= A[j]
 Divide & Conquer Inversion (2)
• When A[i] > A[j], advance j
• When A[i] < A[j], then every element of the
subarray A[m+1..j-1] is strictly smaller than
A[i] and they all create inversions.
– (j-1)-(m+1)-1 = j-m-1 inversions

21
Counting inversions when A[i] <= A[j]
 Divide & Conquer Inversion (3)
• When we copy elements from the end of
the left subarray to the final array, each
element that is copied also generates an
inversion with respect to ALL elements of
the right subarray
– There are r-m such elements.
– Add this to the inversion counter

22
Counting inversions when A[i] <= A[j]
Divide & Conquer Inversion:
Code

23
Divide & Conquer Inversion:
Example

Divide & Conquer Inversion Counting

24