Transcript sorting algorithms

Mark Allen Weiss: Data Structures and Algorithm Analysis in Java
Chapter 7:
Sorting Algorithms
Merge Sort
Lydia Sinapova, Simpson College
Merge Sort
Basic Idea
Example
Analysis
Animation
2
Idea
Two sorted arrays can be merged
in linear time with N comparisons
only.
Given an array to be sorted,
consider separately
its left half and its right half,
sort them and then merge them.
3
Characteristics
 Recursive algorithm.
 Runs in O(NlogN) worst-case running
time.
Where is the recursion?

Each half is an array that can be sorted
using the same algorithm - divide into
two, sort separately the left and the right
halves, and then merge them.
4
Example
5
Merge Sort Code
void merge_sort ( int [ ] a, int left, int right)
{
if(left < right) {
int center = (left + right) / 2;
merge_sort (a,left, center);
merge_sort(a,center + 1, right);
merge(a, left, center + 1, right);
}
}
6
Analysis of Merge Sort
Assumption: N is a power of two.
For N = 1 time is constant (denoted by 1)
Otherwise:
time to mergesort N elements =
time to mergesort N/2 elements +
time to merge two arrays each N/2 el.
7
Recurrence Relation
Time to merge two arrays each N/2
elements is linear, i.e. O(N)
Thus we have:
(a) T(1) = 1
(b) T(N) = 2T(N/2) + N
8
Solving the Recurrence
Relation
T(N) = 2T(N/2) + N
divide by N:
(1) T(N) / N = T(N/2) / (N/2) + 1
Telescoping: N is a power of two, so we can
write
(2) T(N/2) / (N/2) = T(N/4) / (N/4) +1
(3) T(N/4) / (N/4) = T(N/8) / (N/8) +1
…….
T(2)
/2
= T(1) / 1
+1
9
Adding the Equations
The sum of the left-hand sides will be equal to
the sum of the right-hand sides:
T(N) / N + T(N/2) / (N/2) + T(N/4) / (N/4) +
… + T(2)/2 =
T(N/2) / (N/2) + T(N/4) / (N/4) + ….
+ T(2) / 2 + T(1) / 1 + LogN
(LogN is the sum of 1’s in the right-hand sides)
10
Crossing Equal Terms,
Final Formula
After crossing the equal terms, we get
T(N)/N = T(1)/1 + LogN
T(1) is 1, hence we obtain
T(N) = N + NlogN = (NlogN)
Hence the complexity of the Merge Sort
algorithm is (NlogN).
11