Chapter 1

Analysis of Algorithms
Sorting Algorithms

Design and Analysis of Computer

Algorithms
The Sorting Problem
• Input:
– A sequence of n items → a1, a2, . . . , an
19 17 33 11 15 13
• Output:
– A permutation (reordering) a1’, a2’, . . . , an’ of the input
sequence to be in non-descending order such that
– a1’ ≤ a2’ ≤ · · · ≤ an’. 11 13 15 17 19 33

• Approach (techniques):
– Selection Sort - Incremental Technique (simple)
– Insertion Sort - Incremental Technique (simple)
– Merge Sort - Divide and conquer Technique
Sorting Algorithms:
• Insertion Sort
• Selection Sort
• Merge Sort
Insertion Sort

To insert 12, we need to make

room for it by moving first 36
and then 24.
Insertion Sort
Insertion Sort
Insertion
0 1 2 3 4
11 13 15 17 19 ...... X=8
To insert an item (X) to a sorted
0 1 2 3 4 5
list of size n
8 11 13 15 17 19

1. Loop:
Shift up all list elements > (X) 0 1 2 3 4
2. Insert (X) 11 13 15 17 19 ...... X=16
3. n=n+1 0 1 2 3 4 5
8 13 15 16 17 19

Performance:
0 1 2 3 4
The insertion costs:
11 13 15 17 19 ...... X=25
Worst case (all elements > X) ➔O(n)
Best case (larger list element <= X) ➔ 0 1 2 3 4 5
O(1) 11 13 15 17 19 25
Insertion Sort
input array

5 2 4 6 1 3
At each iteration, the array is divided in two sub-arrays:

left sub-array right sub-array

5 2 4 6 1 3
sorted unsorted

left sub-array right sub-array

sorted unsorted
Insertion Sort
Input list ➔ 5 2 4 6 1 3

Iteration Resulted
1 array

Iteration
5
Iteration
2

Iteration
Iteration 4
3
Insertion Sort
k
0 1 | 2 3 4 5

Iteration 1
k
0 1 2 | 3 4 5
Iteration 2

k
0 1 2 3 | 4 5
Iteration 3

Iteration 4 0 1 2 3
k4 | 5

Iteration 5 k
0 1 2 3 4 5

At the end of each pass k through the algorithm given above, the entries
in the sublist {a0; a1; … ; ak } are first k entries of the original list, but in
sorted order.
The Insertion-Sort Algorithm

works by iterating through an array and sorting elements in a linear fashion.

1. The algorithm starts at element 0 in an array and considers element sorted.
2. It then looks at the first element to the right of our sorted array that just contains
our 0 position element
3. It then inserts this unsorted element in to it’s correct location.
4. Our sorted array now has 2 elements
5. The algorithm proceed to insert the next element into the correct position in our
sorted array until the entire list has been sorted.
Python code
The Insertion-
Sort Algorithm
key

key

key

algorithm Insertion (A[1..n])

1. initialize: sort A[0]
2. for k = 1 to n {
3. key = A[k]
4. j=k
5. while j > 0 and A[j-1] > key{
6. A[j] = A[j-1]
7. j ← j -1}
8. A[j] = key
9. } c/c++ like code
Insertion Sort
At the end of each pass k through the algorithm given above, the entries in the
sublist {a0; a1; … ; aj } are first k entries of the original list, but in sorted order.

K=5
Insertion Sort performance
At each step of insertion sort:
• The outer loop (K) will be executed
(n-1) times.
• Each time K is incremented (i.e each pass):
• list A[0, …, k-1] is already sorted.
• A[k] is inserted to the part of the list
A[0, …, k].
• The insertion requires [ 0 to K-1] or k
steps.
• In the worst case, the insertion takes k
steps.

• The inner loop is executed

𝑛−1
𝑛 𝑛−1
෍ 𝑘 = 1 + 2 + 3 + ⋯+ 𝑛 − 1 = ⇒ 𝑂(𝑛2 )
2
𝑘=1
Best case O(n)
when list is sorted or “almost sorted”
Consider an array of five already sorted elements
• Take element 11, as it is first element we keep it as it
is.
• Step 1:
• Take element 13, look for element that falls before it (that
is element 11), as 13>11, therefore no further need for
looking at elements that fall before 11.
• Step 2:
• Take element 15, look for element that falls before it(that
is element 13), as 15>13, therefore no further need for
looking at elements that fall before 13. 11 13 15 17 19
• Step 3:
• Take element 17, look for element that falls before it(that In the best case: The
is element 15), as 17>15, therefore no further need for
looking at elements that fall before 15. insertion requires 1 step.
So, inner loop is executed :
• Step 4: n
• Take element 19, look for element that falls before it(that
is element 17), as 19>17, therefore no further need for  1 = ( n )
j =2
looking at elements that fall before 17.
Sorting Algorithms:
• Insertion Sort
• Selection Sort
• Merge Sort
Locate the smallest element
0 1 2 3 4 5

5 2 4 6 1 3 K= 0

1. K=0 // location of min in A[0→n-1]

0 1 2 3 4 5
2. Loop: j=1→ n-1
5 2 4 6 1 3 J =1 K= 1
If A[j] < A[k] then k=j
3. Return k 0 1 2 3 4 5
// note: k in [0 → n-1] 5 2 4 6 1 3 J=2 K= 1

0 1 2 3 4 5
5 2 4 6 1 3 J=3 K= 1

0 1 2 3 4 5
Performance:
5 2 4 6 1 3 J=4 K= 4
The Algorithm costs:
➔O(n)
0 1 2 3 4 5
in all cases
5 2 4 6 1 3 J=5 K= 4
Swap the first item with the first smallest
item in the list 0 1 2 3 4 5

5 2 4 6 1 3 K= 0
0 1 2 3 4 5
1. min element is at k= 0 5 2 4 6 1 3 J =1 K= 1
2. Loop: j=1→ n-1
If A[j] < A[k] then k=j 0 1 2 3 4 5
3. Return k as location of min in 5 2 4 6 1 3 J=2 K= 1
A[0→n-1] 0 1 2 3 4 5
4. If (k != 0) 5 2 4 6 1 3 J=3 K= 1
Swap (A[0],A[K])
0 1 2 3 4 5
5 2 4 6 1 3 J=4 K= 4
Performance:
Swap() cost constant time 0 1 2 3 4 5
The algorithm costs: 5 2 4 6 1 3 J=5 K= 4
➔O(n)
in all cases 0 1 2 3 4 5
1 2 4 6 5 3 Swap (A[0],A[4])
Selection Sort

No need for
1st smallest 6th iteration
swap

swap 5th smallest

swap 2nd smallest

swap 4th smallest

swap 3rd smallest
The Selection-Sort Algorithm
Selection Sort Algorithm
Input: An array A[0..n-1] of n elements.
Output: A[0..n-1] sorted in nondecreasing order.
1. for i  0 to n - 2
2. k  i //search for min starts at i , K is index of min
3. for j  i + 1 to n-1 {Find the i th smallest element.}
4. if A[j] < A[k] then k  j
5. end for
6. if k  i then swap( A[i] , A[k]) //swap the beginning of the list with min
7. end for

• The outer loop (i) : represents the search space for the min elements
[1→n-1] , [2→n-1] , [3→n-1] ..... [n-2→ n-1]
size of the search space: n-1 n-2 n-3 ...... 1
to find 1st smallest 2nd smallest 3rd smallest (n-2) smallest
• Inner loop(j) : find the location of the min in the specified space
Selection-Sort

0 1 2 3 4 5 0 1 2 3 4 5

Iteration(1) 5 2 4 6 1 3 Iteration(4) 1 2 3 6 5 4
i= 0 , j(1→5) i= 3 , j(4→5)
K=4 swap K=5 swap
1 2 3 4 5 6
1 2 4 6 5 3

0 1 2 3 4 5 0 1 2 3 4 5
Iteration(2) Iteration(5) 1 2 3 4 5 6
1 2 4 6 5 3
i= 1 , j(2→5) i= 4 , j(5→5)
K=1 no swap K=4 no swap
1 2 4 6 5 3 1 2 3 4 5 6

0 1 2 3 4 5
Iteration(3) 1 2 4 6 5 3 0 1 2 3 4 5
i= 2 , j(3→5) The resulted
K=5 swap list after 5 1 2 3 4 5 6
1 2 3 6 5 4 iterations
Selection Sort Algorithm
Input: An array A[1..n] of n elements.
Output: A[1..n] sorted in nondecreasing order.
1. for i  0 to n - 2
2. k  i
3. for j  i + 1 to n-1 {Find the i th smallest element.}
4. if A[j] < A[k] then k  j
5. end for The Worst case
6. if k  i then swap( A[i] , A[k]) Analysis
7. end for
⚫ The outer loop iterates n-1 times.
⚫ The inner loop iterates n-i times
⚫ There is a comparison in each iteration.
⚫ The sort method executes swap() once on each iteration of its outer
loop
⚫ The total number of swap is O(n)

The inner loop is executed

𝑛−1

෍ 𝑛 − 𝑖 = 𝑛 − 1 + … . +3 + 2 + 1 =
𝑛 𝑛−1
⇒ 𝑂(𝑛2 )
The total cost of the
𝑖=1
2 selection sort is :
O(n2)
Selection Sort Algorithm
Input: An array A[1..n] of n elements.
Output: A[1..n] sorted in nondecreasing order. 11 13 15 17 19
1. for i  0 to n - 2
2. k  i The Best case
3. for j  i + 1 to n-1 {Find the i th smallest element.} Analysis
4. if A[j] < A[k] then k  j List is already sorted
5. end for
6. if k  i then swap( A[i] , A[k])
The total cost of the
7. end for
selection sort is :
⚫ The outer loop iterates n-1 times.
O(n2)
⚫ The inner loop iterates n-i times
⚫ There is a comparison in each iteration.
⚫ The sort method executes swap() once on each iteration of its outer
loop
⚫ The total number of swap is O(1)

The inner loop is executed The selection sort algorithm

𝑛−1
𝑛 𝑛−1 is bounded by the inner loop
෍ 𝑛 − 𝑖 = 𝑛 − 1 + … . +3 + 2 + 1 = ⇒ 𝑂(𝑛2 ) Not the swap operation
2
𝑖=1
Selection-Sort
Sorting Algorithms:
• Insertion Sort
• Selection Sort
• Merge Sort
Merge sort
divide and conquer approach
8 2 9 4 5 3 1 6

midpoint

1. Divide the list in two at the midpoint

2. Conquer each side in turn (by recursively sorting)
3. Merge two halves together (merge two sorted arrays into
a third Sorted array)
Merge sort Algorithm
Initial call ➔ MERGE‐SORT (A, 1, n)

MERGE‐SORT (A, p, r)
if p < r //Check for base case
1. then mid ← [( p + r) / 2] //Divide
2. MERGE‐SORT (A,p, mid) //Conquer
3. MERGE‐SORT (A, mid+1, r) //Conquer
4. MERGE (A, p, mid, r) //Combine

merge two sorted arrays into a third Sorted array

MERGE (A, p, mid, r) ➔
• merges the sorted lists A[p,mid] and A[mid+1, r]
• The result is A[p,r] is sorted
Merge sort (A,p,r)
1. mid ← [( p + r) / 2]
p mid r

left mid+1
right
p mid r

2. MERGE‐SORT (A, p, mid) 3. MERGE‐SORT (A, mid+1, r)

p mid mid+1 r

Left = n/2 right = n/2

4. MERGE (A, p,mid, r)

1 2 3 4 5 6 7 8
Initial unsorted list 5 2 4 7 1 3 2 6
1 2 3 4 5 6 7 8
5 2 4 7 1 3 2 6

1 2 3 4 5 6 7 8
5 2 4 7 1 3 2 6
Initial 1 2 3 4 5 6 7 8
unsorted 5 4 1 2
list
2 7 3 6

2 5 4 7 1 3 2 6

1 2 3 4 5 6 7 8

2 4 5 7 1 2 3 6

Final sorted list 1 2 2 3 4 5 6 7

1 2 3 4 5 6 7 8
Merging Two Sorted Lists

• To merge two sorted arrays into a third Sorted array.

• Repeatedly compare the two least elements and copy the
smaller of the two
Linear‐time merging
Merge( A, 5,8,13)

p q r
....... 5 6 7 8 9 10 11 13 .......

A ....... 2 5 16 20 3 7 11 33 .......

L 2 5 16 20 ∞ R 3 7 11 33 ∞
1 2 3 4 5 1 2 3 4 5
Merge( A, 5,8,13)

p q r
....... 5 6 7 8 9 10 11 13 .......

A ....... 2 5 16 20 3 7 11 33 .......

L 2 5 16 20 ∞ R 3 7 11 33 ∞
1 2 3 4 5 1 2 3 4 5
i j

A ....... .......
....... 5 6 7 8 9 10 11 13 .......
k
Merge( A, 5,8,13)

p q r
....... 5 6 7 8 9 10 11 13 .......

A ....... 2 5 16 20 3 7 11 33 .......

L 2 5 16 20 ∞ R 3 7 11 33 ∞
1 2 3 4 5 1 2 3 4 5
i j

A ....... 2 .......
....... 5 6 7 8 9 10 11 13 .......
k
Merge( A, 5,8,13)

p q r
....... 5 6 7 8 9 10 11 13 .......

A ....... 2 5 16 20 3 7 11 33 .......

L 2 5 16 20 ∞ R 3 7 11 33 ∞
1 2 3 4 5 1 2 3 4 5
i j

A ....... 2 3 .......
....... 5 6 7 8 9 10 11 13 .......
k
Merge( A, 5,8,13)

p q r
....... 5 6 7 8 9 10 11 13 .......

A ....... 2 5 16 20 3 7 11 33 .......

L 2 5 16 20 ∞ R 3 7 11 33 ∞
1 2 3 4 5 1 2 3 4 5
i j

A ....... 2 3 5 .......
....... 5 6 7 8 9 10 11 13 .......
k
Merge( A, 5,8,13)

p q r
....... 5 6 7 8 9 10 11 13 .......

A ....... 2 5 16 20 3 7 11 33 .......

L 2 5 16 20 ∞ R 3 7 11 33 ∞
1 2 3 4 5 1 2 3 4 5
i j

A ....... 2 3 5 7 .......
....... 5 6 7 8 9 10 11 13 .......
k
Merge( A, 5,8,13)

p q r
....... 5 6 7 8 9 10 11 13 .......

A ....... 2 5 16 20 3 7 11 33 .......

L 2 5 16 20 ∞ R 3 7 11 33 ∞
1 2 3 4 5 1 2 3 4 5
i j

A ....... 2 3 5 7 11 .......
....... 5 6 7 8 9 10 11 13 .......
k
Merge( A, 5,8,13)

p q r
....... 5 6 7 8 9 10 11 13 .......

A ....... 2 5 16 20 3 7 11 33 .......

L 2 5 16 20 ∞ R 3 7 11 33 ∞
1 2 3 4 5 1 2 3 4 5
i j

A ....... 2 3 5 7 11 16 20 .......
....... 5 6 7 8 9 10 11 13 .......
k
Merge( A, 5,8,13)

p q r
....... 5 6 7 8 9 10 11 13 .......

A ....... 2 5 16 20 3 7 11 33 .......

L 2 5 16 20 ∞ R 3 7 11 33 ∞
1 2 3 4 5 1 2 3 4 5
i j

A ....... 2 3 5 7 11 16 20 33 .......
....... 5 6 7 8 9 10 11 13 .......
k
Merging performance

Ɵ(n1 + n2)=Ɵ(n)

Ɵ(n1 + n2)=Ɵ(n)

Total Complexity is linear Ɵ(n)

Space Complexity
n is the size of the original list
Ɵ(n) Best, worst, average
1 2 3 4 5 6 7 8
mergesort(A,1,8)
9 3 2 7 6 1 18 4

9 3 2 7 6 1 18 4

9 3 2 7 6 1 18 4

9 3 2 7 6 1 18 4

3 9 2 7 1 6 4 18

2 3 7 9 1 4 6 18

1 2 3 4 6 7 9 18
MGS(A,1,8) 5 2 4 7 1 3 2 6
MGS(A,1,4) MGS(A,5,8)

5 2 4 7 1 3 2 6
MGS(A,1,2) MGS(A,3,4) MGS(A,5,7) MGS(A,7,8)

5 2 4 7 1 3 2 6
MGS(A,1,1) MGS(A,2,2) MGS(A,3,3) MGS(A,4,4) MGS(A,5,5) MGS(A,6,6) MGS(A,7,7) MGS(A,8,8)

5 2 4 7 1 3 2 6

2 5 4 7 1 3 2 6
merge(A,1,1,2) merge(A,3,3,4) merge(A,5,5,6) merge(A,7,7,8)

2 4 5 7 1 2 3 6
merge(A,1,2,4) merge(A,5,6,8)

1 2 2 3 4 5 6 7
merge(A,1,4,8)
Analyzing merge sort
MERGE‐SORT (A, p, r) T(n)=?
if p < r //Check for base case
1. then mid ← [( p + r) / 2] //Divide 1
2. MERGE‐SORT (A,p, mid) //Conquer T(n/2)
3. MERGE‐SORT (A, mid+1, r) //Conquer T(n/2)
4. MERGE (A, p, mid, r) //Combine Ɵ(n)

• The base case occurs when n = 1.

• Divide: compute the middle of the subarray, D(n) = (1).
• Conquer: Recursively solve 2 subproblems, each of size n/2
• ⇒ a =2 and b = 2.
• Combine: MERGE on an n‐element subarray takes O(n) time
• ⇒ C(n) = O(n).
Analyzing merge sort

Each level has n nodes

At the bottom level, a tree with

h levels n nodes.

The total complexity of

merging = O(n) in each
level.

h = logn.

The total cost is cn*logn = O(nlogn).

Merge Sort Analysis
Merge Sort Analysis
At a level k the number of sequences is 2k each sequence has a size = (n/ 2k )

𝒏
𝟐𝒌 × 𝒄 = 𝐜𝐧
𝟐𝒌

𝒏
2𝐥𝐨𝐠𝐧 × 𝒄 = 𝐜𝐧
𝟐𝒍𝒐𝒈𝒏

𝑻𝒐𝒕𝒂𝒍 = 𝒄 𝒏𝒍𝒐𝒈𝒏
𝑻𝒐𝒕𝒂𝒍 𝒓𝒖𝒏𝒏𝒊𝒏𝒈 𝒕𝒊𝒎𝒆 𝒊𝒔 Ɵ(𝒏𝒍𝒐𝒈𝒏)
𝑻𝒐𝒕𝒂𝒍 𝒔𝒑𝒂𝒄𝒆 𝒊𝒔 Ɵ(𝒏) The complexity is tightly
bounded to (nlogn)
Thank you