COMP 3203
Introduction to Data Structures
and Algorithms
Merge Sort
Sorting Algorithms and Average Case
Number of Comparisons
Simple Sorts
Selection Sort
Bubble Sort O(N2)
Insertion Sort
More Complex Sorts
O(N log N)
Quick Sort
Merge Sort
2 By Dr. Farha Al Kharusi, DCS, SQU
Merge Sort: Motivation
If I have two helpers, I’d…
• Give each helper half the array to
sort
• Then I get back the sorted sub-
arrays and merge them.
What if those two helpers each had
two sub-helpers?
And the sub-helpers each had two
sub-sub-helpers? And…
3 By Dr. Farha Al Kharusi, DCS, SQU
Merge Sort
Merge is a divide-and-conquer algorithm
Let us try divide-and-conquer on the following list of letters:
H E M G B K A Q F L P D R C J N
Break it into two lists:
H E M G B K A Q
F L P D R C J N
Sort them:
A B E G H K M Q
C D F J L N P R
Is putting these two lists together easier than sorting the whole
list?
4 By Dr. Farha Al Kharusi, DCS, SQU
Merge Sort
Combining two sorted lists into one sorted list is called merging.
A B E G H K M Q
C D F J L N P R
Starting at the front of both lists, we keep picking the smallest letter:
*A* B E G H K M Q
C D F J L N P R
*B* E G H K M Q
C D F J L N P R
E G H K M Q
*C* D F J L N P R
E G H K M Q
*D* F J L N P R
etc.
5 By Dr. Farha Al Kharusi, DCS, SQU
Divide-and-Conquer Sorts
6 By Dr. Farha Al Kharusi, DCS, SQU
Subdivide the sorting task
H E M G B K A Q F L P D R C J N
H E M G B K A Q F L P D R C J N
7 By Dr. Farha Al Kharusi, DCS, SQU
Subdivide again
H E M G B K A Q F L P D R C J N
H E M G B K A Q F L P D R C J N
H E M G B K A Q F L P D R C J N
8 By Dr. Farha Al Kharusi, DCS, SQU
And again
H E M G B K A Q F L P D R C J N
H E M G B K A Q F L P D R C J N
H E M G B K A Q F L P D R C J N
H E M G B K A Q F L P D R C J N
9 By Dr. Farha Al Kharusi, DCS, SQU
And one last time
H E M G B K A Q F L P D R C J N
H E M G B K A Q F L P D R C J N
H E M G B K A Q F L P D R C J N
H E M G B K A Q F L P D R C J N
H E M G B K A Q F L P D R C J N
10 By Dr. Farha Al Kharusi, DCS, SQU
Now merge
H E M G B K A Q F L P D R C J N
H E M G B K A Q F L P D R C J N
H E M G B K A Q F L P D R C J N
E H G M B K A Q F L D P C R J N
H E M G B K A Q F L P D R C J N
11 By Dr. Farha Al Kharusi, DCS, SQU
And merge again
H E M G B K A Q F L P D R C J N
H E M G B K A Q F L P D R C J N
E G H M A B K Q D F L P C J N R
E H G M B K A Q F L D P C R J N
12 By Dr. Farha Al Kharusi, DCS, SQU
And again
H E M G B K A Q F L P D R C J N
A B E G H K M Q C D F J L N P R
E G H M A B K Q D F L P C J N R
13 By Dr. Farha Al Kharusi, DCS, SQU
And one last time
A B C D E F G H J K L M N P Q R
A B E G H K M Q C D F J L N P R
14 By Dr. Farha Al Kharusi, DCS, SQU
Done
A B C D E F G H J K L M N P Q R
15 By Dr. Farha Al Kharusi, DCS, SQU
Divide-and-Conquer Approach in Merge Sort
If n = 1
Terminate (every one-element list is already sorted)
If n > 1
Partition elements into two or more sub-collections
Sort each partition
Combine into a single sorted list
16 By Dr. Farha Al Kharusi, DCS, SQU
Merge Sort Algorithm
Cut the array in half.
Sort the left half.
Sort the right half.
Merge the two sorted halves into one sorted array.
74 36 ... 95 75 29 ... 52
[first] [middle] [middle + 1] [last]
36 74 ... 95 29 52 ... 75
17 By Dr. Farha Al Kharusi, DCS, SQU
Merge Sort - Code
// Recursive Merge Sort Algorithm
void MergeSort (ItemType[ ] values, int first, int last)
// Pre: first < last
// Post: Array values[first .. Last] sorted into ascending order
{
if (first < last) // general case
{
int middle = (first + last) / 2;
MergeSort(values, first, middle);
MergeSort(values, middle + 1, last);
// now merge two subarrays
// values [first .. middle] with
// values [middle + 1 .. last]
Merge(values, first, middle, last);
} // if
} // MergeSort
18 By Dr. Farha Al Kharusi, DCS, SQU
Using Merge Sort Algorithm with N = 16
16
8 8
4 4 4 4
2 2 2 2 2 2 2 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
19 By Dr. Farha Al Kharusi, DCS, SQU
Merge Algorithm
The central sub-problem is the merging of two sorted
arrays into one single sorted array
let us suppose that we have two disjoint ordered arrays
a[0]... a[N-1] and b[0] … b[M-1] of integers and we wish
to merge them into a third array c[0] ... c [N+M-1].
The obvious strategy is to choose successively for c the
smallest element from a and b.
a 12 33 35 45
b 15 42 55 65 75
c 12 15 33 35 42 45 55 65 75
20 By Dr. Farha Al Kharusi, DCS, SQU
Merge
a: 12 33 35 45 i: 0
b: 15 42 55 65 75 j: 0
c: k: 0
i < 4 and j < 5: a[ i ] <= b[ j ] ???
21 By Dr. Farha Al Kharusi, DCS, SQU
Merge
a: 12 33 35 45 i: 0
b: 15 42 55 65 75 j: 0
c: 12 k: 0
i < 4 and j < 5: a[ i ] <= b[ j ] YES
22 By Dr. Farha Al Kharusi, DCS, SQU
Merge
a: 12 33 35 45 i: 1
b: 15 42 55 65 75 j: 0
c: 12 k: 1
i < 4 and j < 5: a[ i ] <= b[ j ] ???
23 By Dr. Farha Al Kharusi, DCS, SQU
Merge
a: 12 33 35 45 i: 1
b: 15 42 55 65 75 j: 0
c: 12 15 k: 1
i < 4 and j < 5: a[ i ] <= b[ j ] NO
24 By Dr. Farha Al Kharusi, DCS, SQU
Merge
a: 12 33 35 45 i: 1
b: 15 42 55 65 75 j: 1
c: 12 15 k: 2
i < 4 and j < 5: a[ i ] <= b[ j ] ???
25 By Dr. Farha Al Kharusi, DCS, SQU
Merge
a: 12 33 35 45 i: 1
b: 15 42 55 65 75 j: 1
c: 12 15 k: 2
i < 4 and j < 5: a[ i ] <= b[ j ] YES
26 By Dr. Farha Al Kharusi, DCS, SQU
Merge
a: 12 33 35 45 i: 1
b: 15 42 55 65 75 j: 1
c: 12 15 33 k: 2
i < 4 and j < 5: a[ i ] <= b[ j ] YES
27 By Dr. Farha Al Kharusi, DCS, SQU
Merge
a: 12 33 35 45 i: 2
b: 15 42 55 65 75 j: 1
c: 12 15 33 k: 3
i < 4 and j < 5: a[ i ] <= b[ j ] ???
28 By Dr. Farha Al Kharusi, DCS, SQU
Merge
a: 12 33 35 45 i: 2
b: 15 42 55 65 75 j: 1
c: 12 15 33 35 k: 3
i < 4 and j < 5: a[ i ] <= b[ j ] YES
29 By Dr. Farha Al Kharusi, DCS, SQU
Merge
a: 12 33 35 45 i: 3
b: 15 42 55 65 75 j: 1
c: 12 15 33 35 k: 4
i < 4 and j < 5: a[ i ] <= b[ j ] ???
30 By Dr. Farha Al Kharusi, DCS, SQU
Merge
a: 12 33 35 45 i: 3
b: 15 42 55 65 75 j: 1
c: 12 15 33 35 42 k: 4
i < 4 and j < 5: a[ i ] <= b[ j ] NO
31 By Dr. Farha Al Kharusi, DCS, SQU
Merge
a: 12 33 35 45 i: 3
b: 15 42 55 65 75 j: 2
c: 12 15 33 35 42 k: 5
i < 4 and j < 5: a[ i ] <= b[ j ] ???
32 By Dr. Farha Al Kharusi, DCS, SQU
Merge
a: 12 33 35 45 i: 3
b: 15 42 55 65 75 j: 2
c: 12 15 33 35 42 45 k: 5
i < 4 and j < 5: a[ i ] <= b[ j ] YES
33 By Dr. Farha Al Kharusi, DCS, SQU
Merge
a: 12 33 35 45 i: 4
b: 15 42 55 65 75 j: 2
c: 12 15 33 35 42 45 k: 6
i == 4
34 By Dr. Farha Al Kharusi, DCS, SQU
Merge
a: 12 33 35 45 i: 4
b: 15 42 55 65 75 j: 2
c: 12 15 33 35 42 45 55 k: 6
i ==4: take b[ j ]
35 By Dr. Farha Al Kharusi, DCS, SQU
Merge
a: 12 33 35 45 i: 4
b: 15 42 55 65 75 j: 3
c: 12 15 33 35 42 45 55 k: 7
j<5
36 By Dr. Farha Al Kharusi, DCS, SQU
Merge
a: 12 33 35 45 i: 4
b: 15 42 55 65 75 j: 3
c: 12 15 33 35 42 45 55 65 k: 7
j<5
37 By Dr. Farha Al Kharusi, DCS, SQU
Merge
a: 12 33 35 45 i: 4
b: 15 42 55 65 75 j: 4
c: 12 15 33 35 42 45 55 65 k: 8
j<5
38 By Dr. Farha Al Kharusi, DCS, SQU
Merge
a: 12 33 35 45 i: 4
b: 15 42 55 65 75 j: 4
c: 12 15 33 35 42 45 55 65 75 k: 8
j<5
39 By Dr. Farha Al Kharusi, DCS, SQU
Merge
a: 12 33 35 45 i: 4
b: 15 42 55 65 75 j: 5
c: 12 15 33 35 42 45 55 65 75 k: 9
j == 5
40 By Dr. Farha Al Kharusi, DCS, SQU
Merge - Code
static void MergeAB( Item[] c, Item[] a, int N, Item[] b, int M)
{
for (int i=0, j=0, k=0; k<M+N; k++)
{
if (i==N)
{
c[k] = b[j++];
continue;
}
if (j==M)
{
c[k] = a[i++];
continue;
}
if (a[i] < b[j])
c[k] = a[i++];
else
c[k] = b[j++];
} // for
} // MergeAB
41 By Dr. Farha Al Kharusi, DCS, SQU
Example 1
Given a = {3, 20, 66, 87, 101} and
b = { -1, 40, 52, 74, 213, 412, 970}
Array c = {-1, 3, 20, 40, 52, 66, 74, 87, 101, 213, 412, 970} after
calling the function MergeAB(c, a, 5, b, 7).
Discussion: The above function uses extra space proportional
to the size of arrays a and b. It is valuable to have a method
that could merge a[left] … a[m] and a[m+1] ... a[right] into
a[left] … a[right] without using extra space by moving the
element around within a[left] … a[right]. However, this is
complicated. Also the loop includes two tests to determine
whether the ends of the two inputs have been reached.
42 By Dr. Farha Al Kharusi, DCS, SQU
Abstract In-Place Merge
The algorithm emphasizes on using the interface merge(a,
left, m, right) to indicate that the merge subroutine will
put the result of merging a[left] … a[m] and a[m+1] …
a[right] into a single ordered list leaving the result in
a[left] … a[right].
43 By Dr. Farha Al Kharusi, DCS, SQU
Merge - Code
static void Merge(Item[] a, int left, int middle, int right)
{
int i,j;
static Item[] aux = new Item[a.length];
for (i = middle + 1; i > left; i--)
aux[i-1] = a[i-1];
// add the next list in aux array in reverse order
for (j = middle; j < right; j++)
aux[right + middle - j] = a[j+1];
// order the two lists in aux array into array a
for (int k = left; k <= right; k++)
if (aux[j] < aux[i])
a[k] = aux[j--];
else
a[k] = aux[i++];
} // Merge
44 By Dr. Farha Al Kharusi, DCS, SQU
Example 2
Suppose we have an array a = {10, 4, 6, 3, 8, 2, 5, 7}
Show the partition tree of the divide-and-conquer after we call
the function mergeSort(a, 0, 7)
Also, show how the merge process.
45 By Dr. Farha Al Kharusi, DCS, SQU
Analysis (Recurrence equation of merge
sort)
Assume N is a power of 2,
ì c , N =1 ü
ï 1 ï
T (N) = í æNö ý
ï 2T ç ÷ + c2 N , N =2 ï
k
î è2ø þ
By Substitution:
T(N) = 2T(N/2) + c2N
T(N/2) = 2T(N/4) + c2N/2
T(N) = 4T(N/4) + 2 c2N
T(N) = 8T(N/8) + 3 c2N
T(N) = 2iT(N/2i) + ic2N
46 By Dr. Farha Al Kharusi, DCS, SQU
Analysis (Recurrence equation of merge sort)
Assuming N = 2k, the growth ends when we get T(1) on
right side; this happens when i=k T(N) = 2kT(1) + kc2N
Since 2k=N, we know k = log N; since T(1) = c1, we get
T(N) = c1N + c2N log N
Thus an upper bound for TmergeSort(N) is O(N log N)
47 By Dr. Farha Al Kharusi, DCS, SQU
Merge Sort of N elements: How many comparisons?
The entire array can be subdivided into halves only log N times.
Each time it is subdivided, function Merge is called to re-combine the
halves. Function Merge uses a temporary array to store the merged
elements. Merging is O(N) because it compares each element in the sub
arrays.
Copying elements back from the temporary array to the values array is also
O(N).
MERGE SORT IS O(N log N).
48 By Dr. Farha Al Kharusi, DCS, SQU
Testing
To thoroughly test our sorting methods we should vary
the size of the array they are sorting
Vary the original order of the array-test
Reverse order
Almost sorted
All identical elements
49 By Dr. Farha Al Kharusi, DCS, SQU
Reference
Part of this slide set is prepared or/and extracted from
the following references:
Data Structures & Algorithm Analysis in Java; Clifford A. Shaffer;
Dover Publications Inc.; 3rd edition, 2011 – Chapter 7
Algorithms in C++; Robert Sedgewick; Addison-Wesely
Publishing Company Inc.; 3rd edition, 1998 – Chapter 8
50 By Dr. Farha Al Kharusi, DCS, SQU
