Designing Sorting algorithms
There are many ways to design an algorithm.
Insertion sort uses an incremental approach: having
sorted the sub-array A[1…j - 1], we insert the single
element A[ j] into its proper place, yielding the sorted
sub-array A[1…j].
Another approach to design is the divide-and-conquer
approach which has a recursive structure to solve a
given problem;
Merge Sort
Quick Sort
1
The divide-and-conquer
approach
Recursive in structure
Divide the problem into several smaller sub-
problems that are similar to the original but
smaller in size
Conquer the sub-problems by solving them
recursively. If they are small enough, just solve
them in a straightforward manner.
Combine the solutions to create a solution to the
original problem
2
An Example: Merge Sort
Divide: Divide the n-element sequence to be
sorted into two subsequences of n/2
elements each
Conquer: Sort the two subsequences
recursively using merge sort.
Combine: Merge the two sorted
subsequences to produce the sorted answer.
3
Merge Sort
To sort n numbers
if n = 1 done!
recursively sort 2 lists of numbers n/2 and n/2 elements
merge 2 sorted lists in O(n) time
Strategy
break problem into similar (smaller) subproblems
recursively solve subproblems
combine solutions to answer
4
Merge Sort Procedure
The procedure MERGE-SORT(A, p, r) sorts the elements
in the sub-array A[ p…r].
The divide step simply computes an index q that partitions
A[ p…r] into two sub-arrays: A[ p…q], containing n/2
elements, and A[ q + 1…r], containing n/2 elements.
5
Merge Sort Procedure
To sort the entire sequence A ={A[1], A[2], . . . ,
A[ n]}, we make the initial call
MERGE-SORT( A, 1, length[ A]),
where length[ A] = n.
6
Merge
The key operation of the merge sort algorithm is the
merging of two sorted sequences in the "combine" step.
To perform the merging, we use an auxiliary procedure
MERGE(A, p, q, r), where A is an array and p, q, and r
are indices numbering elements of the array such that p ≤
q < r.
The procedure assumes that the sub-arrays A[ p…q] and
A[ q + 1…r] are in sorted order. It merges them to form a
single sorted sub-array that replaces the current sub-array
A[ p…r].
7
Merge algorithm
8
.Merge algorithm cont
The operation of lines 10-17 in the call MERGE(A, 9, 12, 16).
9
.Merge algorithm cont
The operation of lines 10-17 in the call MERGE(A, 9, 12, 16)
10
Merge Sort
11
Merge Sort
12
.Merge Sort cont
[8, 3, 13, 6, 2, 14, 5, 9, 10, 1, 7, 12, 4]
[8, 3, 13, 6, 2, 14, 5] [9, 10, 1, 7, 12, 4]
[8, 3, 13, 6] [2, 14, 5] [9, 10, [7, 12, 4]
1]
[8, [13, 6] [2, 14] [5] [9, 10] [1] [7, 12] [4]
3]
[8] [3] [13] [6] [2] [14] [9] [10] [7] [12]
13
.Merge Sort cont
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13,14]
[2, 3, 5, 6, 8, 13, 14] [1, 4, 7, 9, 10,12]
[3, 6, 8, 13] [2, 5, 14] [1, 9, [4, 7, 12]
10]
[3, [6, 13] [2, 14] [5] [9, 10] [1] [7, 12] [4]
8]
[8] [3] [13] [6] [2] [14] [9] [10] [7] [12]
14
Analysis of Merge Sort
Statement Effort
MergeSort(A, left, right) { T(n)
if (left < right) { (1)
mid = floor((left + right) / 2); (1)
MergeSort(A, left, mid); T(n/2)
MergeSort(A, mid+1, right); T(n/2)
Merge(A, left, mid, right); (n)
}
}
Divide: computing the middle takes O(1)
Conquer: solving 2 sub-problem takes 2T(n/2)
Combine: merging n-element takes O(n)
15
.Analysis of Merge Sort cont
16
// Until we reach either end of either L or M, pick larger among
elements L and M and place them in the correct position at
// Merge sort in C A[p..r]
#include <stdio.h> while (i < n1 && j < n2) {
// Merge two subarrays L and M into arr
if (L[i] <= M[j]) {
void merge(int arr[], int p, int q, int r) {
arr[k] = L[i];
// Create L ← A[p..q] and M ← A[q+1..r]
i++;
int n1 = q - p + 1;
} else {
int n2 = r - q;
arr[k] = M[j];
j++;
int L[n1], M[n2];
}
k++;
for (int i = 0; i < n1; i++)
}
L[i] = arr[p + i];
// When we run out of elements in either L or M,
for (int j = 0; j < n2; j++) // pick up the remaining elements and put in A[p..r]
M[j] = arr[q + 1 + j];
while (i < n1) {
// Maintain current index of sub-arrays and main array arr[k] = L[i];
int i, j, k; i++;
i = 0; k++;
j = 0; }
k = p; while (j < n2) {
arr[k] = M[j];
j++;
k++;
} 17
// Merge sort in C
// Print the array
// Divide the array into two subarrays, sort them
and merge them
void printArray(int arr[], int size) {
void mergeSort(int arr[], int l, int r) {
for (int i = 0; i < size; i++)
if (l < r) {
printf("%d ", arr[i]);
// m is the point where the array is divided into printf("\n");
two subarrays }
int m = l + (r - l) / 2; int main() {
int arr[] = {6, 5, 12, 10, 9, 1};
mergeSort(arr, l, m); int size = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, m + 1, r);
mergeSort(arr, 0, size - 1);
// Merge the sorted subarrays
merge(arr, l, m, r); printf("Sorted array: \n");
} printArray(arr, size);
} }
18
