CSE221: Algorithms
D & C Based Sorting Algorithms
Prepared by: A B M Muntasir Rahman [MUNR]
Divide & Conquer Approach
Divide the problem (instance) into subproblems.
Conquer the subproblems by solving them recursively.
Combine the solutions to subproblems.
Examples
● Binary/Ternary Search
● Merge Sort
● Quick Sort
● Maximum Sum Subarray
● Karatsuba’s Algorithm for Multiplication etc.
Time Complexity: aT(n/b) + f(n)
Merge Sort
● A divide & conquer sorting algorithm
● Recursively divides the array into
smaller subarrays and then by sorting
these subarrays while merging obtains
the sorted array.
How does Merge Sort work?
● Divide: Divide the array or dataset recursively into
two halves until it can no more be divided.
● Conquer: Each smallest subarray is automatically
sorted individually using the merge sort algorithm.
● Merge: The sorted subarrays are merged back
together in sorted order and the process continues
until all elements from both subarrays have been
merged.
Merge Sort (Simulation)
9 4 5 2 1 7 4 6
9 4 5 2 1 7 4 6
9 4 5 2 1 7 4 6
9 4 5 2 1 7 4 6
Merge Sort (Simulation)
1 2 4 4 5 6 7 9
2 4 5 9 1 4 6 7
4 9 2 5 1 7 4 6
9 4 5 2 1 7 4 6
Merge Sort (Pseudocode)
mergeSort(arr)
if (len(arr) <= 1)
return arr
mid = len(arr) // 2
left = mergeSort(arr[:mid])
right = mergeSort(arr[mid:])
return merge(left, right)
Merge Sort (Pseudocode)
merge(left, right)
while (i < len(left))
a = arrayOf(len(left) + len(right))
a[k] = left[i]
i, j, k = 0, 0, 0
i = i + 1
while (i < len(left) && j < len(right))
k = k + 1
if (left[i] <= right[j])
while (j < len(right))
a[k] = left[i]
a[k] = right[j]
i = i + 1
j = j + 1
else
k = k + 1
a[k] = right[j]
j = j + 1
return a
k = k + 1
Time Complexity Analysis
mergeSort(arr) T(n)
if (len(arr) <= 1)
return arr
mid = len(arr) // 2 1
left = mergeSort(arr[:mid]) T(n/2)
right = mergeSort(arr[mid:]) T(n/2)
return merge(left, right) n
Time Complexity Analysis
∴ T(n) = 2T(n/2) + n
Solving with tree/substitution/master method,
T(n) = O(nlogn)
Merge Sort (Properties)
● Time Complexity:
○ Best/Average/Worst Case: O(nlogn).
● Space Complexity:
○ Best/Average/Worst case: O(n).
● Stable: Yes.
● Inplace: No.
● Suitable for larger arrays. Unsuitable for smaller
arrays and requires additional memory store the
merged subarrays.
Quicksort
● A divide and conquer sorting
algorithm.
● Picks a pivot and partitions the input
array around the picked pivot by
placing it in it’s correct position in
sorted array.
How does Quicksort work?
● Divide: The array or dataset is divide into subarrays
by selecting a pivot element. While dividing, the
pivot should be positioned in such a way that all
elements less than pivot are on the left side and
elements greater than the pivot are on the right side
of the pivot. This process continues until each
subarray contains a single element.
● Conquer: Each smallest subarray is automatically
sorted at this point.
● Combine: All subarrays are combined to form a
sorted array.
Quicksort (Simulation)
Pivot
7 2 1 6 8 5 3 4
partitio <= 4 Pivo >4
n t
2 1 3 4 7 6 8 5
Pivot Pivot
2 1 3 7 6 8 5
partition Pivo Pivo
partitio
t t n
2 1 3 5 7 6 8
Pivot
2 7 6 8
Quicksort (Pseudocode)
quickSort(arr, start, end){ partition(arr, start, end){
if (start >= end){ pivot = arr[end]
return arr pIndex = start
} for(int i = start, i <= end-1; i++){
pIndex = partition(arr, start, if (arr[i] <= pivot){
end) swap(arr[i], arr[pIndex])
quickSort(arr, start, pIndex - pIndex = pIndex + 1
1) }
quickSort(arr, pIndex + 1, end) }
return arr swap(arr[pIndex], arr[end])
} return pIndex
}
Time Complexity Analysis
quickSort(arr, start, end){ T(n)
if (start >= end){
return arr
}
n
pIndex = partition(arr, start,
end) T(n/2)
quickSort(arr, start, pIndex - T(n/2)
1)
quickSort(arr, pIndex + 1, end)
return arr
}
Time Complexity Analysis
∴ T(n) = 2T(n/2) + n
Solving with tree/substitution/master method,
T(n) = O(nlogn)
Worst Case
1 2 3 4 5 6 7 8
● For above sorted array, if we choose first element as pivot, there will
be no left subarray. Again, if we choose last element as pivot, there
will be no right subarray.
● In such cases, the recurrence relation becomes T(n) = T(n - 1) + n.
Which, by solving, we get O(n2) in worst case.
● However, this can be easily avoided by choosing mid or other
element as pivot.
Quick Sort (Properties)
● Time Complexity:
○ Best/Average Case: O(nlogn).
○ Worst Case: O(n2).
● Space Complexity:
○ Best/Average Case: O(log n).
○ Worst Case: O(n).
● Stable: No.
● Inplace: Yes (in best/average case).
● Suitable for larger arrays. Unsuitable for smaller
arrays and is not a stable sorting algorithm.
