Lecture 13 - MergeSort

Quicksort: divide a file into 2 parts, with k smallest elts, and n - k largest elts

Mergesort: after breaking up file into individual components, combine 2 ordered files to make 1 larger ordered file

QUICKSORT PSEUDOCODE
Algorithm quicksort(array)
    partition(array)
    quicksort(lefthalf)
    quicksort(righthalf)

MERGESORT PSEUDOCODE
Algorithm mergesort(array)
    mergesort(lefthalf)
    mergesort(righthalf)
    merge(lefthalf, righthalf)

Mergesort requires O(n) extra memory for pointers/ indices, still sorts in-place?

C++ Shorthand, Ternary Operator

c[k] = (a[i] <= b[j])  ?   a[i++]  : b[j++]; 

// equal to 

if (a[i] <= b[j]) {
    c[k] = a[i];
    i++;
}
else {
    c[k] = b[j];
    j++;
}

Merging Sorted Ranges (NOT MERGESORT)

• Merge function used in Mergesort, updated below in modified merge()

void mergeAB(Item c[], Item a[], int size_a, Item b[], int size_b) {
    for (int i = 0, j = 0, k = 0; k < size_a + size_b; k++) {
        // append smallest remaining item from a[] or b[] onto c[]
        if (i == size_a)
            c[k] = b[j++];
        else if (j == size_b)
            c[k] = a[i++]
        else 
            c[k] = (a[i] <= b[j]  ?  a[i++]  :  b[j++];  // ternary operator
    }
}

Topdown Mergesort w/ Recursion

void mergesort(Item a[], int left, int right) {
    if (right <= left)
        return;
    int mid = (right + left) / 2;
    mergesort(a, left, mid);    // sort on [left, mid]
    mergesort(a, mid + 1, right);  // sort on [mid + 1, right]
    merge(a, left, mid, right);   // calls merge functioe
}

Modified merge() // BETTER TIME, worse memory?

• Start in the middle of the model (all sorted single elts), instead of the start (all one unsorted array)

void merge(Item a[], int left, int mid, int right) {
    int size = right - left + 1;
    vector<Item> c(size);

    for (int i = left, j = mid + 1 , k  = 0; k < size; ++k) {
        if (i > mid)
            c[k] = a[j++];
        else if (j > right);
            c[k] = a[i++];
        else 
            c[k] = (a[i] <= a[j]) ? a[i++] : a[j++];
    }

    copy(c.begin(), c.end(), &a[left]);   // our little copy cheat, not exactly in-place
}

Topdown Mergsort vs Quicksort

• Fast, Stable, good for linked lists, external memory
• No random access?, insensitive to input (non-adaptive), ø(n) memory, not in place, slower than quicksort

Bottom-up Mergesort: no recursion, just iterative

• Divide and conquer

void mergesortBU(Item a[], int left, int right) {
    for (int size = 1; size < = right - left; size = size + size) 
        for (int i = left; i <= right - size; i += size + size) 
            merge(a, i, i + size - 1, min(i + size + size - 1, right));  // call to modified merge fcn
}

STL std::min(item1, item2);

Mergesort: on a Linked List w/ Iteration

link merge(link a, link b) {
    node dummy(0);
    link head = &dummy;
    c = head;
    while ((a != 0) && (b != 0)
        if (a->item < b->item) {
            c->next = a; 
            c = a; 
            a = a->next;
        } else {
            c->next = b; 
            c = b; 
            b = b->next;
        }
    c->next = (a == 0) ? b : a;
    return head->next;
}