Algorithms
Seminar 1 - Sorting
This seminar aims at discovering two different sorting algorithms: insertion sort and merge sort.
The questions will focus on understanding how these two algorithms work, check their correctness
and compute their complexity. We recall below the sorting problem statement:
Input: A sequence of n numbers ha1 , a2 , ..., an i
Question: Find a permutation ha01 , a02 , ..., a0n i of the original sequence such that ∀i ≤
n, a0i ≤ a0i+1 .
⚠️ Given there is no specific convention in pseudocode on indexes, you are free to choose the index
at which you start (e.g., 0 or 1) and the one at which you end (e.g., n-1 or n).
1 Insertion sort
Insertion sort is the method that some people use to sort cards without realizing it: going from left
to right, each new card is inserted to the (originally empty) sorted set of cards at the beginning of
the deck. As the sorting procedure goes on, the set of sorted cards at the beginning of the deck
expands until the entire deck is sorted.
1. Using the description of insertion sort above, write the arrays obtained after each step of the
algorithm applied on the sequence h49, 28, 7, 1, 10, 15i.
Mark in a different color the numbers which are sorted.
Answer #1
We obtain the following series of arrays:
• 49, 28, 7, 1, 10, 15
• 28, 49, 7, 1, 10, 15
• 7, 28, 49, 1, 10, 15
• 1, 7, 28, 49, 10, 15
• 1, 7, 10, 28, 49, 15
• 1, 7, 10, 15, 28, 49
2. Given your answer to the previous question, write in pseudocode the insertion sort algorithm.
1
Answer #2
Algorithm 1: INSERTION-SORT
Data: An array A of size n.
Result: The sorted array.
for i = 2 to n do
key = A[i]
j =i−1
while j 6= 0 and A[j] > key do
A[j + 1] = A[j]
j =j−1
end
A[j + 1] = key
end
3. State a loop invariant for this algorithm, then proceed to show it is correct.
Answer #3
The (outer-)loop invariant is the following one:
“At the start of each iteration of the for loop, the subarray A[1 : i − 1]
consists of the elements originally in A[1 : i − 1], but in sorted order.”
Initialization
When i = 2, the subarray only consists of the first element A[1], which is sorted by
default.
Maintenance
During the loop, all the elements A[i − 1], A[i − 2], ... are shifted to the right to insert
A[i] to the right position. After A[i] has reached its final position, the subarray A[1 : i]
is sorted.
Termination When exiting the outer loop, i = n + 1, hence the subarray A[1 : n] is
sorted, which is precisely A.
4. Following each line of the algorithm you just wrote, express the complexity of each operation
as a function of n (some operations will not be in closed form, but they can still be expressed
using parameters depending on n). Write the overall complexity Tn .
Answer #4
As seen during lectures, arithmetic operations take constant time, so lines 3, 4, 6, 7
and 8 all correspond to a O(1) complexity. It remains to count how many iterations
the loops contain.
The for loop is run n − 1 times. However, it is not necessarily clear how many times
the while loop executes for each iteration of the for loop. Therefore, it is best to use
a variable ti to express this number, until we can find P
a closed-form expression for it.
Summing over every iteration of the for loop gives O ( i=2 ti ) complexity.
n
Finally, we have
n
!
X
Tn = O(n) + O ti
i=2
5. What is the best-case scenario for insertion sort? What about the worst?
2
Answer #5
The best-case scenario is when the list is already sorted. Conversely, the worst-case
scenario is when the list is already sorted, but in the reverse order (from left to right).
6. How is Tn expressed in the best-case scenario? In the worst? Give the time complexity of
insertion sort for each scenario.
Answer #6
For the best-case scenario, ti = 1 ∀i since no shift is needed. This yields
n
! n
!
X X
Tn = O(n) + O ti = O(n) + O 1 = O(n) + O(n − 1) = O(n)
i=2 i=2
The complexity is linear for the best-case scenario.
For the worst case, on the other hand, at each iteration, A[i] needs to be shifted to the
beginning of the array. It means that i shifts are necessary, which gives ti = i. So,
n
! n
!
X X
Tn = O(n) + O ti = O(n) + O i
i=2 i=2
n(n + 1)
= O(n) + O − 1 = O(n2 )
2
The complexity is quadratic for the worst-case scenario.
2 Merge sort
Merge sort is a divide-and-conquer method: first, the initial problem is divided into smaller prob-
lems, which are supposedly easier to solve, or conquer. Finally, the solutions to the subproblems are
combined to obtain the solution to the initial problem.
Regarding the sorting problem, one such method is merge sort: the initial array is split in two
over and over until the subarrays contain only a single element. At this point, the algorithm builds
back arrays of increasingly larger sizes by comparing the leftmost elements of each subarray to obtain
a sorted output that contains the elements of both. This is repeated until the recovered array has
the same size as the initial one.
1. Using the description above, write the arrays obtained after each step of the merge sort algo-
rithm applied on the sequence h49, 28, 7, 1, 10, 19, 21, 15i.
Answer #1
Following the divide-conquer-merge steps yields:
3
49 28 7 1 10 19 21 15
49 28 7 1 10 19 21 15
49 28 7 1 10 19 21 15
49 28 7 1 10 19 21 15
28 49 1 7 10 19 15 21
1 7 28 49 10 15 19 21
1 7 10 15 19 21 28 49
2. Before we write the complete merge sort algorithm, we need to write the MERGE(A, l, m,
r) algorithm, which merges together the two sorted subarrays A[l : m] and A[m + 1 : r]. The
algorithm needs to:
• Split A into two subarrays (which we assume are sorted).
• Empty the subarrays by popping the smallest element out of the two.
• Check that both subarrays are empty by iterating over the potential remaining elements
in one of the two.
Answer #2
Algorithm 2: MERGE
Data: An array A, three indices l, m and r.
Result: The sorted subarray A[l : r].
nL = m − l + 1
nR = r − m
Let L (resp. R) be an empty array of size nL (resp. nR )
for i = 1 to nL do
L[i] = A[l + i − 1]
end
for j = 1 to nR do
R[j] = A[m + j]
end
i=1
j=1
k=l
4
while i ≤ nL and j ≤ nR do
if L[i] ≤ R[j] then
A[k] = L[i];
i = i + 1;
end
else
A[k] = R[j];
j = j + 1;
end
k = k + 1;
end
while i ≤ nL do
A[k] = L[i];
i = i + 1;
k = k + 1;
end
while j ≤ nR do
A[k] = R[j];
j = j + 1;
k = k + 1;
end
3. What is the time complexity of this algorithm?
Answer #3
The complexity of the MERGE algorithm is very straightforward to compute. All
operations which are performed are O(1), since they are all arithmetic ones. We can
thus look at the cost of each loop:
• the first for loop is O(nL ) = O(n)
• the second is O(nL ) = O(n)
• the first while loop is O(min(nL , nR )) = O(n)
• the remaining two while loops are O(n) for the same reasons as the first two for
loops.
Therefore, the total complexity is expressed as a sum of O(n) functions, which is O(n)
by linear combination.
4. Using the previous answers, write the complete algorithm for merge sort.
Hint: Use a recursive approach.
5
Answer #4
Algorithm 3: MERGE-SORT
Data: An array A, left and right bounds l and r.
Result: The sorted subarray A[l : r].
if l ≥ r then
return
end
m = b (l+r)
2 c
MERGESORT(A, l, m)
MERGESORT(A, m + 1, r)
MERGE(A, l, m, r)
5. Express the time complexity of merge sort Tn with a recurrence equation.
Answer #5
Merge sort calls itself twice on half the instance, and makes a call to MERGE which is
O(n). The recurrence equation is therefore written:
Tn = 2 Tn/2 + O(n)
6. With the assumption that n is an exact power of 2, represent the recursion as a binary tree
where the value of each element is the right-hand term in the recurrence equation (only draw
the first levels and the last).
Answer #6
c2 n
c2 n2 c2 n2
c2 n4 c2 n4 c2 n4 c2 n4
c1 c1 c1 c1 c1 c1 c1 c1
To understand this tree, we can rewrite the recurrence equation as follows: assuming
n to be an exact power of 2 with the base case n = 20 = 1, we can write
if n = 1
(
c1
Tn =
2 Tn/2 + c2 n otherwise
At each level, the Tn/2 term disappears to leave only the c2 n term.
7. How many levels are in this tree? What is the time complexity of each level? Deduce the
overall time complexity for merge sort.
Answer #7
The height of this binary tree is blog2 nc = log2 n since we assume n to be an exact
power of 2. Adding the root level, that gives us log2 n + 1 levels in total.
The complexity of each level is always the same: c2 n (except for the last one: c1 n).
This is because we compensate every 1/2 division by twice the number of terms in the
sum.
6
Therefore, the overall complexity c2 n log2 n + c1 n = O(n log n).
Note: Although one could argue that this proof only works when n is a power of 2, it
is because the more general case relies on the master theorem which is not part of the
syllabus.
8. (Optional) Based on the same assumption that n is an exact power of 2, and assuming T2 = 2
as the base case, with all constants equal to 1, use a proof by induction to show the previous
result.
Answer #8
Again, assuming n to be an exact power of 2, which is equivalent to write n = 2k for
some k ∈ N∗ :
if n = 2
(
2
Tn =
2 Tn/2 + n otherwise
We want to show that Tn = n log n. The induction is conducted on k rather than n.
Hence, we assume the assumption holds for a fixed k, and compute the recurrence for
k + 1:
T (2k+1 ) = 2 T (2k ) + 2k+1
= 2 · 2k log(2k ) + 2k+1
= k 2k+1 + 2k+1
= (k + 1)2k+1
= 2k+1 log(2k+1 )
