COMP2521
Data Structures & Algorithms
Week 8.3
Merge Sort
1
In this lecture
Why?
We need some algorithms better than O(n^2) for large
data sets.
What?
Merge sort
2
Mergesort Overview
The key of this approach is that it’s recursive.
1. Split the array into two roughly equal sized partitions
2. Recursively sort each of the partitions
3. Merge the two partitions into a new sorted array
3 . 1
Mergesort Overview
Source: https://levelup.gitconnected.com/visualizing-designing-and-analyzing-the-merge-sort-algorithm-cf17e3f0371f
Split / Divide
Merge
3 . 2
Implementation
void mergesort(Item a[], int lo, int hi)
{
int mid = (lo + hi) / 2; // mid point
if (hi <= lo) return;
mergesort(a, lo, mid);
mergesort(a, mid+1, hi);
merge(a, lo, mid, hi);
}
int main() {
int nums[10] = {32,45,17,22,94,78,64,25,55,42};
mergesort(nums, 0, 9);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
Merge sort is kind of like a binary tree split where the re-merging
happens post-fix.
The function "merge" has to merge two sorted arrays back together.
4 . 1
Implementation
void merge(Item a[], int lo, int mid, int hi) {
int i, j, k, nitems = hi - lo + 1;
Item *tmp = malloc(nitems * sizeof(Item));
i = lo; j = mid + 1; k = 0;
// scan both segments, copying to tmp
while (i <= mid && j <= hi) {
if (less(a[i], a[j]))
tmp[k++] = a[i++];
else
tmp[k++] = a[j++];
}
// copy items from unfinished segment
while (i <= mid) tmp[k++] = a[i++];
while (j <= hi) tmp[k++] = a[j++];
//copy tmp back to main array
for (i = lo, k = 0; i <= hi; i++, k++)
a[i] = tmp[k];
free(tmp);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
The merge function
4 . 2
Performance
Split / Divide
We have to split our
list log(N) times
Merge
We have to merge N
numbers exactly
log(N) times
This part requires
extra memory 🙁
O(log(N))
O(N * log(N))
5 . 1
Performance
Mergesort has both a best and worst case of
O(N*log(N))
Whether the list is fully sorted, or fully reverse
sorted, the same steps are taken
This makes it time-wise generally better than
quicksort - however - we need extra memory
for this.
5 . 2
Linked Lists
Whilst mergesort typically operates on arrays, it's also possible to do it
on linkedlists. We won't go into any detail on this.
6
Feedback
7