CS计算机代考程序代写 data structure algorithm COMP2521

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