Algorithms Analysis & Design - Lecture 9

Introduction to the Design and Analysis of Algorithms

1. Algorithms
By Mohamed Gamal
© Mohamed Gamal 2024

3. Divide N Conquer

4. Merge Sort Algorithm
–Merge Sort uses the divide-and-conquer approach to break the problem into
smaller sub-problems, solve each sub-problem recursively, and then combine the
results.
–Merge Sort is a comparison-based sorting algorithm that repeatedly compares
pairs of elements to determine their order.
–Merge Sort is typically implemented using recursion, although it can also be
implemented iteratively.

5. Merge Sort Algorithm
1)Divide the array into two halves.
2)Recursively apply Merge Sort to each half.
3)Merge the two sorted halves back together:
a)Compare the elements of the two halves and arrange them in order.
b)Continue merging elements until all elements from both halves are merged into a single sorted array.
4)Repeat the process until the entire array is sorted.
2 8 5 3 9 4 1 7

10. Complexity:
▪Worst Case: ??????(??????log??????)
▪Average Case: ??????(??????log??????)
▪Best Case: ??????(??????log??????)
Advantages:
▪Merge Sort is well-suited for sorting large datasets that do not fit into memory (external sorting)
because it accesses data sequentially and has good performance with large datasets.
▪Merge Sort is a stable sort, meaning that it preserves the relative order of equal elements in the
sorted array.
Disadvantages:
▪Merge Sort is not in-place sorting algorithm since it requires additional space proportional to the
size of the array being sorted.

11. Let ??????(??????) be the number of comparisons made by the merge-sort algorithm.
Recurrence relation equation: ????????????=2??????
??????
2
+?????? and ??????1=0
•Using backward substitution:
??????(??????)=2??????
??????
2
+??????
=22??????
??????
4
+
??????
2
+??????=4??????
??????
4
+2??????
= 42??????
??????
8
+
??????
4
+2??????=8??????
??????
8
+3??????
????????????=2
??????
??????
??????
2
??????

+?????? ??????
=2
log2??????
??????
??????
2
log2??????

+log
2?????? ??????
= ??????log
2??????
??????
2
??????

= 1
2
??????
=??????
??????=log
2??????
Basic Operation
n represents the number of comparisons required
to merge the two sorted halves

12. Divide N Conquer

13. Quick Sort Algorithm
–Quick Sort uses the divide-and-conquer approach to break the problem into
smaller sub-problems, sort each sub-problem recursively, and then combine the
results.
–Quick Sort is typically implemented using recursion, although it can also be
implemented iteratively.
–The choice of the pivot element is crucial for the performance of Quick Sort.
Good pivot selection strategies can significantly improve its efficiency.

15. Note: Pivots shown in bold.

17. Complexity:
▪Worst Case: ??????(??????
2
) – sorted array!
▪Average Case: ??????(??????log??????) – random arrays
▪Best Case: ????????????log?????? – split in the middle
Advantages:
▪Quick Sort is in-place sorting algorithm, meaning it requires only a small, constant amount of additional
memory space.
▪Despite its worst-case scenario, Quick Sort is often faster in practice compared to other ????????????log??????
algorithms like Merge Sort due to its good cache performance and low overhead.
Disadvantages:
▪The worst-case time complexity is ??????(??????
2
), which occurs when the pivot selection consistently results in
highly unbalanced partitions.
▪Quick Sort is not stable, which means it may not preserve the relative order of equal elements.

18. Which algorithm would Obama pick?
Source: http://www.youtube.com/watch?v=k4RRi_ntQc8

19. Thank You!