7. Sorting

Merge sort

0 of 5 activities0%

Reading 1

Stable divide and conquer

Open

Merge sort splits the array in half, sorts each half, then merges two sorted lists.

Time O(n log n) always. Extra O(n) space for the merge buffer. Stable if merge is careful.

Great teaching algorithm for recursion + conquering.

void mergeSort(int l, int r){
  if(r-l<=1) return;
  int m=(l+r)/2;
  mergeSort(l,m);
  mergeSort(m,r);
  merge(l,m,r);
}

Check 2

Open

Merge sort worst-case time is

Fill in 3

Open

Try it 4

Open

Merge [1,4,7] and [2,3,9].

main.cpp

Loading editor…

Program input (stdin)

Output will appear here.

Assignment 5

Open

Read n, n sorted ints, m, m sorted ints. Print merged sorted sequence.

main.cpp

Loading editor…