‫بسم اهلل الرحمن الرحيم‬

‫‪Prof. Ossama Ismail‬‬

 Divide-and-Conquer

Prof. Ossama Ismail

You may read Chapter 4

Divide-and-Conquer
 Recursion in Words of Wisdom

• Philosopher Lao-tzu:
The journey of a thousand miles begins with a single
step

Prof. Ossama Ismail

 divide-and-conquer algorithm

Many useful algorithms are recursive in structure: to solve a

given problem, they call themselves recursively one or more
times to deal with closely related subproblems. These
algorithms typically follow a divide-and-conquer approach:
they break the problem into several subproblems that are
similar to the original problem but smaller in size, solve the
subproblems recursively, and then combine these solutions to
create a solution to the original problem.

5
divide-and-conquer algorithm cont’d

The divide-and-conquer paradigm

involves three steps at each level of the
recursion:
Divide the problem into a number of
subproblems.
Conquer the subproblems by solving
them recursively. If the subproblem sizes
are small enough, however, just solve the
subproblems in a straightforward
manner. 6/60
Prof. Ossama Ismail
 divide-and-conquer algorithm cont’d

The divide-and-conquer technique is the basis of efficient algorithms

for many problems, such as:
Breaking a Stone into Dust
 sorting (e.g., quicksort, merge sort),
 multiplying large numbers (e.g., the Karatsuba algorithm),
 finding the closest pair of points, syntactic analysis (e.g., top-dow
n parsers), and

 divide-and-conquer algorithm cont’d

Parallelism
Breaking a Stone into Dust
Divide-and-conquer algorithms are naturally adapted for execution
in multi-processor machines, especially shared-memory systems
where the communication of data between processors does not need
to be planned in advance because distinct sub-problems can be
executed on different processors.

Prof. Ossama Ismail

 divide-and-conquer algorithm cont’d

Memory access
Divide-and-conquer algorithms naturally tend to make efficient use of
memory caches. The reason is that once a sub-problem is small
enough, it and all its sub-problems can, in principle, be solved within
the cache, without accessing the slower main memory.
D&C algorithms can be designed for important algorithms (e.g.,
sorting, FFTs, and matrix multiplication) to be optimal cache-oblivious
algorithms–they use the cache in a probably optimal way, in an
asymptotic sense, regardless of the cache size.
9/60
Prof. Ossama Ismail
divide-and-conquer algorithm cont’d

Stack size
In recursive implementations of D&C algorithms, one must make sure
that there is sufficient memory allocated for the recursion stack,
otherwise, the execution may fail because of stack overflow.

Stack overflow may be difficult to avoid when using recursive

procedures since many compilers assume that the recursion stack is a
contiguous area of memory, and some allocate a fixed amount of
space for it. Compilers may also save more information in the
recursion stack than is strictly necessary, such as return address,
unchanging parameters, and the internal variables of the procedure.
Thus, the risk of stack overflow can be reduced by minimizing the
parameters and internal variables of the recursive procedure or by
using an explicit stack structure. 10/60
 divide-and-conquer algorithm cont’d

Recursion
Divide-and-conquer algorithms are naturally implemented as recursive
procedures. In that case, the partial sub-problems leading to the one
currently being solved are automatically stored in the procedure call s
tack. A recursive function is a function that calls itself within its
definition.
H.W.
Write a piece of that returns the stack size used by your computer?

11/60
Prof. Ossama Ismail
 divide-and-conquer algorithm cont’d

Method
• Divide problem into subproblems
• Solve subproblems
• If subproblems have same nature as original
problem, the strategy can be applied recursively

• Merge subproblem solutions into solutions for

original problem
 Breaking a Stone into Dust
Break Stone:
You want to ground a stone into dust (very small stones)
What is your first step?
First Step
• Use a hammer and strike the stone
Next Step
• If a stone pieces that result is small enough, we are done with that part
• For pieces that are too large, repeat the
BreakStone process

If the problem is small enough to be solved directly, do it

If not, find a smaller problem and use its solution to create the solution to the
larger problem

Prof. Ossama Ismail

Divide-and-Conquer Algorithm
• Divide-and conquer is a general algorithm design
paradigm:
– Divide: divide the input data S in two or more disjoint
subsets S 1, S 2, S 2…
– Recur: solve the subproblems recursively
– Conquer: combine the solutions for S 1, S 2, …, into a
solution for S
• The base case for the recursion are subproblems of
constant size
• Analysis can be done using recurrence
equations
Divide-and-Conquer Algorithm cont’d

Divide_Conquer(problem P)
{
if Small(P) return S(P);
else {

divide P into smaller instances P1, P2, …, Pk, k1;

Apply Divide_Conquer to each of these subproblems;

return Combine(Divide_Conque(P1),
Divide_Conque(P2),…, Divide_Conque(Pk));
}
}

Prof. Ossama Ismail

 Divide & Conquer recurrence relation

The computing time of Divide & Conquer is

 g ( n) n small
T (n) 
T (n1 )  T ( n2 )  ...  T ( nk )  f ( n) otherwise

– T(n) == time for Divide & Conquer on any input size n.

– g(n) == time to compute the answer directly (for small
inputs)
– f(n) == time for dividing P and combining the solutions.

16
Prof. Ossama Ismail
 A Typical Divide and Conquer Case

a problem of size n

subproblem 1 subproblem 2
of size n/2 of size n/2

Find a solution to Find a solution to

subproblem 1 subproblem 2

Cobine solutions to
Solve the original problem

Prof. Ossama Ismail

Advantages of Divide and Conquer Algorithm
1. Divide and conquer successfully solved one of the biggest problems of
the mathematical puzzle world, the tower of Hanoi.
You might have a very basic idea of how the problem is going to be
solved but dividing the problem makes it easy since the problem and
resources are divided.
2. Is very much faster than other algorithms.
3. The divide and conquer algorithm works on parallelism. Parallel
processing in operating systems handles them very efficiently.
4. The divide and conquer strategy used cache memory without occupying
much main memory. Executing problem in cache memory which is faster
than main memory.
5. Brute force technique and divide and conquer techniques are similar but
divide and conquer is more proficient

18/60
Disadvantages of Divide and Conquer Algorithm
1. Most of the divide and conquer design uses the concept of recursion
therefore it requires high memory management.
2. Memory overuse is possible by an explicit stack.
3. It may crash the system if recursion is not performed properly.

Divide and conquer algorithm vs dynamic programming

Both divide and conquer and dynamic programming divides the given problem into
subproblems and solves those problems. Dynamic programming is used where the
same problem is required to be solved again and again, whereas divide and conquer is
used where the same problem is not required to be calculated again.
For example, in the merge sort algorithm, we don’t need to calculate the same
subproblem again, but while calculating the Fibonacci series we need to calculate the
sum of the past two numbers again and again to get the next number. So, we use
dynamic programming in this case.
19/60
Prof. Ossama Ismail
Factorial Problem

Example: Finding factorial of n >= 1

Divide-and-Conquer
n! = n(n-1)(n-2)…1 Examples
Divide and Conquer
Strategy:
if n = 1: n! = 1 (direct solution),
else: n! = n * (n-1)!
 Divide-and-Conquer
n
* n!
Factorial n Factorial n -1

Prof. Ossama Ismail

 Divide-and-Conquer Examples

• Sorting: mergesort and quicksort

• Binary tree traversals
• Binary search (?)
• Multiplication of large integers
• Matrix multiplication: Strassen’s
algorithm
• Closest-pair and convex-hull algorithms
Sorting Problem
• Optimal number of comparisons
– An algorithm must be able to distinguish which
one of the n! permutations is the correct
permutation.
– Can be viewed as a binary decision tree
– Each permutation corresponds to a leaf in the tree
– The depth of the tree is the number of
comparisons necessary for distinguishing the
sorted permutation
– A binary tree with height h has at most 2h leaves
– A sorting decision tree has height at least log n!
– log n! = O(n log n)
– Comparison-based sorting is O(n log n)
Prof. Ossama Ismail
 : Table for the running time of the algorithms
• In this table, n is the number of elements to be sorted .
• The columns "Best", "Average", and "Worst" give the time
complexity in each case.
• "Memory" denotes the amount of auxiliary storage needed
beyond that used by the list itself.
 Merge Sort

• Merge sort is a sorting algorithm invented by John von

Neumann based on the divide and conquer technique.
It always runs in n log n time, but requires space.

• Developed merge sort for EDVAC in 1963

Prof. Ossama Ismail

 Merge Sort

Prof. Ossama Ismail

Merge Sort Review
The MergeSort function recursively divides the array into smaller
parts and then merges them back together using the Merge
function. The Merge function combines two sorted subarrays into a
single sorted array.

Merge-sort on an input sequence S with n elements

consists of three steps:
– Divide: partition S into two sequences S1 and S2 of
about n/2 elements each
– Recur: recursively sort S1 and S2
– Conquer: merge S1 and S2 into a unique sorted
sequence
Merge Sort Review cont’d
Divide
If q is the half-way point between p and r, then we can split the
subarray A[p..r] into two arrays A[p..q] and A[q+1, r].
Conquer
In the conquer step, we try to sort both the subarrays
A[p..q] and A[q+1, r]. If we haven't yet reached the base
case, we again divide both these subarrays and try to sort them.
Combine
When the conquer step reaches the base step and we get two
sorted subarrays A[p..q] and A[q+1, r] for array A[p..r], we
combine the results by creating a sorted array A[p..r] from two
sorted subarrays A[p..q] and A[q+1, r].
28/60
Prof. Ossama Ismail
Algorithm: Merge-Sort(S,p,r)
A procedure sorts the elements in the sub-array A[left..right]
using divide & conquer and conquer

• MergeSort(A,left,right)
– if left >= right, return
– if left < right then mid  (left  right ) / 2
• MergeSort(A,left,mid)
• MergeSort(A,mid+1,right)
• Merge(A,left,mid,right)
• Starting by calling MergeSort(A,1,n)
29
Algorithm: Merge-Sort(S,p,r) cont’d

30/60
Prof. Ossama Ismail
Algorithm: Merge-Sort(S,p,r) cont’d
void merge(int A[], int lt, int mid, int rt){
1. int i, j, k;
2. int L1 = mid - lt + 1, L2 = rt – mid, left[L1], right[L2]; //Creating tem arrays, additional memory needed
3. for (i = 0; i < L1; i++)
4. left[i] = A[lt + i];
5. for (j = 0; j < L2; j++)
6. right[j] = A[mid + 1 + j];
7. i = j = 0;
8. k = 1;
9. while (i < L1 && j < L2) {
10. if (left[i] <= right[j]) {
11. A[k] = left[i];
12. i++;
13. }
14. else {
15. Arr[k] = right[j];
16. j++;
17. }
18. k++;
19. }
20. while (i < L1)
21. Arr[k++] = left[i++];
22.
23. while (j < L2)
24. Arr[k++] = right[j++];
25. }
31/60
 Recurrence Equation Analysis
 The conquer step of merge-sort consists of merging two sorted sequences,
each with n/2 elements and implemented by means of a doubly linked list,
takes at most cn steps, for some constant b.
 Likewise, the basis case (n < 2) will take at c most steps.
 Therefore, if we let T(n) denote the running time of merge-sort:

 c if n  2
T (n) 
2T (n / 2)  cn if n 2
 We can therefore analyze the running time of merge-sort by finding a closed
form solution to the above equation.
 That is, a solution that has T(n) only on the left-hand side.

Prof. Ossama Ismail

 Analysis of Merge sort
• All cases have same efficiency: θ(n log n)
T(n) = 2T(n/2) + θ(n), T(1) = 0
• Number of comparisons in the worst case is close
to theoretical minimum for comparison-based
sorting:
log2 n! ≈ n log2 n - 1.44n

• Space requirement: θ(n) (not in-place)

Prof. Ossama Ismail

 Solving recurrence eqn. for Mergesort
Iterative Substitution
• In the iterative substitution, or “plug-and-chug,” technique, we
iteratively apply the recurrence equation to itself and see if we can find
a pattern: T ( n) 2T ( n / 2)  cn
2( 2T ( n / 2 2 ))  c ( n / 2))  cn
2 2 T ( n / 2 2 )  2cn
23 T ( n / 23 )  3cn
2 4 T ( n / 2 4 )  4cn
...
2 k T ( n / 2 k )  kcn

Note that base, T(1)=c, case occurs when 2k = n.

That is, k = log2 n. So, Thus, T(n) is O(n log n)

Space Complexity: O(n)

The space complexity is O(n) as it requires additional memory to store the
temporary array during merging.
 Advantages of Merge Sort
• Stable sorting algorithm, maintains the relative order of equal elements.
• Efficient for large datasets with a time complexity of O(n log n).
• Predictable performance, consistently performs well regardless of input data.
• No worst-case scenarios, guarantees reliable sorting performance.
• Memory-efficient, doesn’t require additional memory space for sorting.
Disadvantages of Merge Sort
• Merge sort uses more memory to sort data.
• It doesn’t sort data in the same memory location (not in-place).
• It may not be the best choice for small lists.

35/60
Prof. Ossama Ismail
 The Recursion Tree
• Draw the recursion tree for the recurrence
relation and look for a pattern:
T ( n) 
 c if n  2

2T (n / 2)  cn if n 2
depth T’s size
0 1 n time

bn
1 2 n/2
bn
k 2k n/2k
Total time = cn + n log2 n
bn

…
… … …
(last level plus all previous levels)

Prof. Ossama Ismail

 Merge sort Example
91 3 2 9 88 1 57
4

91 3 2 88 1 57
9 4

The non-recursive version

91 2 9 88 57
3 1 4 of Mergesort starts from
9 3 2 9 8 1 5 4
merging single elements
1 8 7 into sorted pairs.
3 2 9 1 4
91 88 57

2 3 91 1 4 57
9 88

1 2 3 4 57 88 91
9

Prof. Ossama Ismail

 Conclusion
Merge sort is one of the most widely used algorithms in data
structures. Although it is not a space-efficient algorithm, its
time complexity is of the order O(n log n) which is better than
most of the sorting algorithms. Whenever we have an input
size larger than the RAM size, we use merge sort. Thus, merge
sort is very well suited for larger datasets.

In this article, we have studied what is merge sort, how it

works, its applications, drawbacks as well as its
implementation in various programming languages.

38/60
Prof. Ossama Ismail
Merge Sort Complexity
Time Complexity
Best O(n*log n)
Worst O(n*log n)
Average O(n*log n)
Space Complexity O(n)
Stability Yes

Merge Sort Applications

 Inversion count problem
 External sorting
 E-commerce applications
39/60
Prof. Ossama Ismail
 Example: Merge Sort Animation
Problem Sequence Sorted Sequence

57 63 88 33 2 4 91
91 11 1 2 3 4 57 63 88 91

57 63 88 3 2 4 91 1 3 57 63 88 1 2 4 91
91

57 63 88 3 2 4 91 1 57 63
63 3 88 2 4 1 91

57
57 63
63 88
88 33 22 44 91 1 57 63 88 33 2 4 91 1

57 63 88 33 2 44 91
91 1

Prof. Ossama Ismail

Example: Merge Sort

Ref: [Link] 41/60

Prof. Ossama Ismail
 Quicksort
QuickSort is one of the most efficient sorting algorithms and is
based on the splitting of an array into smaller ones. The name
comes from the fact that, quick sort is capable of sorting a list of
data elements significantly faster than any of the common sorting
algorithms. And like Merge sort, Quick sort also falls into the
category of divide and conquer approach of problem-solving
methodology.

Quicksort was developed by British computer scientist Tony Hoa

re in 19579 and published in 19631. It is still a commonly used
algorithm for sorting. Overall, it is slightly faster than merge sort
and heapsort for randomized data.

42/60
Prof. Ossama Ismail
 Quicksort
• Select a pivot (partitioning element) – here, the first element
• Rearrange the list so that all the elements in the first s
positions are smaller than or equal to the pivot and all the
elements in the remaining n-s positions are larger than or
equal to the pivot (see next slide for an algorithm)

A[i] A[i]
p p
• Exchange the pivot with the last element in the first (i.e., )
subarray — the pivot is now in its final position
• Sort the two subarrays recursively
Prof. Ossama Ismail
 Quicksort

Choice of Pivot:
There are many different choices for picking pivots.

1. Always pick the first element as a pivot.

2. Always pick the last element as a pivot

3. Pick a random element as a pivot.

4. Pick the middle as the pivot.

44/60
Prof. Ossama Ismail
Quicksort Example : 1
Sort [57 3 1 9 91 2 4 ]
2 3 1 4 57 91 9 88
1 2 3 4 57 88 91 9
1 2 3 4 57 88 91 9
1 2 3 4 57 88 91 9
1 2 3 4 57 88 91 9
 Quicksort Example : 2

46/60
Prof. Ossama Ismail
 Analysis of Quicksort
• Best case: split in the middle — Θ(n log n)
• Worst case: sorted array! — Θ(n2)
• Average case: random arrays — Θ(n log n)
• Improvements:
– better pivot selection: median of three partitioning
– switch to insertion sort on small subfiles
– elimination of recursion
These combine to 20-257% improvement
• Considered the method of choice for internal sorting of large files (n ≥ 10000)

Quicksort normally uses O(log n) extra memory, stored on the stack. It's not O(n).

Why is quick sort log n space complexity?

 Analysis of Quicksort
Quicksort normally uses O(log n) extra memory, stored on the
stack. It's not O(n).

Why is quick sort log n space complexity?

48/60
Prof. Ossama Ismail
 Binary Search

Binary Search - Is a degenerate divide-and-conquer

search algorithm, no combine phase.
Very efficient algorithm for searching in sorted array:
Problem: Searches for a key in a sorted vector,
returning the index where the key was found or -1
when not found.
Reduces the problem size by half each recursion.

Prof. Ossama Ismail

 Binary Search Algorithm
• A Divide and Conquer Algorithm to find a key in an
array:
• -- Precondition: S is a sorted list >> Check if x ϵ S

binsearch(number n, low, high, S[], x)

if low ≤ high then mid = (low + high) / 2
if x = S[mid] then return mid
elsif x < S[mid] then return
binsearch(n, low, mid-1, S, x)
else return binsearch(n, mid+1, high, S, x)
else return 0 end binsearch
end binsearch

Prof. Ossama Ismail

Example: binsearch(14, 0,13, S, 22)
] [= S

Prof. Ossama Ismail

 Analysis of Binary Search

• Time efficiency
– worst-case recurrence: T (n) = 1 + ( n/2 ), T (1) = 1
solution: T (n) = log2(n+1) = O(log n)

This is VERY fast: e.g., T(109) = 30

• Limitations: must be a sorted array (not linked

list)

Prof. Ossama Ismail

 Closest Pair Problem
The closest pair of points problem or closest pair
problem is a problem of computational geometry:
given n points in metric space, find a pair of points with the
smallest distance between them.

53
Prof. Ossama Ismail
Algorithm
1. Divide the set into..., and recursively compute the distance in each
part, returning the points in each set in sorted order by y-coordinate.
2. Let d be the minimal of the two minimal distances.
3. Eliminate points that lie farther than d apart from l/ Any point outside of this bounding box
4. Merge the two sorted lists into one sorted list in O(n) time. Since the cannot be less than d units from p. It just
remaining points in the y order and compute the distance of each point so happens that because every point in
to its five neighbors.. this box is at least d apart, there can be at
5. If any of these distances is less than d then update d. most six points within it.
Well this is because now we don't need
Time cmplexity to check all n2 points. (proven in the
Step 2 takes O(1) time class)
Step 3 takes O(n) time
Step 4 is a sort that takes O(nlogn) time
Step 5 takes O(n) time (as we saw in the previous section)
Step 6 takes O(1) time

The whole of algorithm ClosestPair takes O(nlogn) = O(nlog2n) time.

54/58
 Closest Pair Problem
• A naive algorithm takes O(n2) time.
• Assumptions:
– No two points have the same x-coordinates
– No two points have the same y-coordinates

• How do we solve this problem in 1 dimensions?

– Sort the number and walk from left to right to find
minimum gap
 Recursive Binary Search
• A Divide and Conquer Algorithm to find a key in an
array:
• -- Precondition: S is a sorted list >> Check if x ϵ S

binsearch(number n, low, high, S[], x)

if low ≤ high then mid = (low + high) / 2
if x = S[mid] then return mid
elsif x < s[mid] then return
binsearch(n, low, mid-1, S, x)
else return binsearch(n, mid+1, high, S, x)
else return 0 end binsearch
end binsearch
Prof. Ossama Ismail
Interview question ??
Question 1 :
How to sort a 1000 GB file with ram size is 4 GB only. Which
algorithm or data structure we need to use to sort these files?

Question 2 :
How would you sort a text file full of phone numbers. You do not
have enough memory to load all the file contents at once and sort
them. You should write back the sorted list to the file in the end.

Question 3 :
Given 2 files find common words. Both files are too large to be
loaded in memory.
57/60
Prof. Ossama Ismail
 External sorting
External sorting is a class of sorting algorithms that can handle massive amounts
of data. External sorting is required when the data being sorted do not fit into the main
memory of a computing device (usually RAM) and instead they must reside in the
slower external memory, usually a disk drive.

Thus, external sorting algorithms are external memory algorithms and thus applicable
in the external memory model of computation.

External sorting algorithms generally fall into two types, distribution sorting, which
resembles quicksort, and external merge sort, which resembles merge sort.

The latter typically uses a hybrid sort-merge strategy. In the sorting phase, chunks of
data small enough to fit in main memory are read, sorted, and written out to a
temporary file. In the merge phase, the sorted subfiles are combined into a single larger
file.

58/60
Prof. Ossama Ismail
 External merge sort
One example of external sorting is the external merge sort algorithm,
For example, for sorting 900 megabytes of data using only 100 megabytes of RAM:

1. Read 100 MB of the data in main memory and sort by some conventional method, like quicksort.
2. Write the sorted data to disk.
3. Repeat steps 1 and 2 until all the data is in sorted 100 MB chunks (there are 900MB / 100MB = 9 chunks),
which now need to be merged into one single output file.
4. Read the first 10 MB (= 100MB / (9 chunks + 1)) of each sorted chunk into input buffers in main memory
and allocate the remaining 10 MB for an output buffer. (In practice, it might provide better performance to
make the output buffer larger and the input buffers slightly smaller.)
5. Perform a 9-way merge and store the result in the output buffer. Whenever the output buffer fills, write it to
the final sorted file and empty it. Whenever any of the 9 input buffers empties, fill it with the next 10 MB of
its associated 100 MB sorted chunk until no more data from the chunk is available. This is the key step that
makes external merge sort work externally—because the merge algorithm only makes one pass sequentially
through each of the chunks, each chunk does not have to be loaded completely; rather, sequential parts of the
chunk can be loaded as needed.

59/60
Prof. Ossama Ismail
 Questions ?

Prof. Ossama Ismail