The Angry Birds — Red

In-spite of being one of the angry birds. Red deserves a separate, and deeper look.

Red — angrybirds

Mergesort

The Mergesort falls under the divide and conquer algorithms. It works by dividing the array into two halves recursively, let’s say it divides array[p…r] into array[p…q], and array[q+1…r]. Then sort each half, and merge the two sorted halves into a single sorted half array[p…r].

Mergesort Overview — algs4.cs.princeton.edu
Mergesort is the default sorting algorithm in Java for objects, C++ & Python stable sort, Firefox JavaScript, …etc. While Quicksort is used in Java for primitives, Visual C++, Python, Chrome JavaScript, …etc.

Implementation

— sort

It does three operations recursively; sort left half array[lo…mid], sort right half array[mid+1…hi], then merge them into a sorted half array[lo…hi].

An array of 1 element is considered sorted.
public void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
if (hi <= lo) return; // base condition
    // lo + hi may overflow if >= 2^32(integer size)
int mid = lo + (hi - lo) / 2;

sort(a, aux, lo, mid);
sort(a, aux, mid + 1, hi);
merge(a, aux, lo, mid, hi);
}

Initially, you need to create the auxiliary aux[] array just once, and send it as a parameter to the sort method, along with the array you want to sort, the first and last indexes.

public static void sort(Comparable[] a) {
Comparable[] aux = new Comparable[a.length];
sort(a, aux, 0, a.length-1);
}

— merge

Given an array divided into two halves, each half is sorted. Merge them into a sorted array. So, the merge method does the following:

  1. Copy array a[] into a temporary array aux[]. The auxiliary array will be used for comparison, while the original array will be re-filled with sorted values.
  2. Define three pointers; i, j, & k. The ‘i’ points to current element on the left half in aux[], ‘j’ points to the current element on the right half, and ‘k’ points to the current element in array a[].
  3. Compare aux[i] and aux[j]. Take the smaller element and copy it to a[k]. If ‘i’ is exhausted, meaning i > mid, keep inserting the elements at aux[j], and vice-versa.
public void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
// precondition: a[lo...mid] and a[mid+1...hi] are sorted subarrays

// Copy array a[] into a temporary array aux[].
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}

// Merge the two subarrays back into sorted a[lo...hi]
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
}

Trace

Besides from the code implementation. It’s important to visualize how Mergesort works, and understand the recursive function calls.

Trace a recursive Mergesort — wikipedia

Analysis

Time →The complexity is O(N LogN) in the worst case.

It always takes (N LogN) compares, and (6 N LogN) array access to sort an array of size N.

We divide the array into two subarrays, and each subarray is divided into two subarrays and so on, until a subarray can no longer be divided by 2(size of 1). This takes O(LogN); the depth of the tree or recursive function calls.

In every level of recursive function calls tree, we traverse all the array elements in merge() method. This takes O(N); N compares and 6N array access.

So, the complexity = depth of recursive calls * time at every level = O(N LogN).

Mergesort Analysis — khanacademy

Memory → We need extra space for the aux[] array of size N. Unlike Selection, Insertion, and Shell sorts, we sort in-place.

Improvements

Could we even improve the algorithm we’ve seen for Mergesort? And the answer is Yes.

1. Use Insertion Sort For Small Arrays

Since the Mergesort is not efficient for the tiny arrays or small sub arrays, as there will be overhead for the recursive calls. You can use Insertion sort whenever the array size is small(≤~ 7).

if (hi <= lo + CUTOFF - 1) {      // Is the array size <= CUTOFF(~7)
insertionSort(array, lo, hi);
return;
}
The optimum value of the CUTOFF to insertion sort is system-dependent, but any value between 5 and 15 is likely to work well in most situations.

2. Stop If Already Sorted

Before calling merge(). Is the biggest element in the left half ≤ smallest element in the right half? If so, no need to call merge() method.

if(!less(a[mid+1], a[mid])) return;
merge(a, aux, lo, mid, hi);

3. Eliminate The Copy To Auxiliary Array

It can be done by switching roles of a[] and aux[] recursively. Now, we don’t need to copy all values in array a[] into aux[] in merge() method. This improvement will save time but not memory as aux[] still exists.

— sort

public void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
// ...

// Switch roles of aux[] and a[] arrays
sort(aux, a, lo, mid);
sort(aux, a, mid + 1, hi);
    /* 2. Stop If Already Sorted (See Above)
If you're going to use this improvement.
You need to copy the a[] into aux[]
    if(!less(a[mid+1], a[mid])){ 
for (int i = lo; i <= hi; i++) aux[i] = a[i];
return;

} */
    merge(a, aux, lo, mid, hi);
}

Initially, you need to initialize aux[] and sets aux[i] = a[i] for each ‘i’, or assign a copy.

public static void sort(Comparable[] a) {
// for (int i = 0; i < a.length; i++) aux[i] = a[i];
Comparable[] aux = a.clone();
sort(aux, a, 0, a.length-1);
}

— merge

public void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
// precondition: a[lo...mid] and a[mid+1...hi] are sorted subarrays
    // Merge the two subarrays into sorted aux[lo...hi]
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if (i > mid) aux[k] = a[j++];
else if (j > hi) aux[k] = a[i++];
else if (less(a[j], a[i])) aux[k] = a[j++];
else aux[k] = a[i++];
}
}

Bottom-up Mergesort

The Mergesort algorithm we’ve seen was called “top-down”. It’s the pure recursion. There is another one called “buttom-up” Mergesort, where we don’t use recursion.

Implementation

Loop through the array, merging every two consecutive subarrays of size 1. Repeat for sorted subarrays of size 2, 4, 8, …etc.

Remember An array of 1 element is considered sorted.
public void sort(Comparable[] a) {
int N = a.length;
Comparable[] aux = new Comparable[N];
for (int sz = 1; sz < N; sz *= 2) {
for (int lo = 0; lo < N-sz; lo += sz+sz) {
int mid = lo+sz-1;
int hi = Math.min(lo+sz+sz-1, N-1);
merge(a, aux, lo, mid, hi);
}
}
}

Why Increment lo by sz+sz?

Because in every loop, we are merging every two consecutive sub arrays of sz. So, the next loop we want to get into the next subarray at index lo+sz+sz.

As an example, If sz = 2, lo = 0, mid = 1, hi = 3. Therefore next loop lo should equals to 4.

Why use Math.min(lo+sz+sz-1, N-1)?

Because consider the case when the array’s size is not multiple of 2. As an example, If N=10, sz=8, lo=0, mid=7, hi=lo+sz+sz-1 = 15 (out of the boundaries!).

The hi will be out of the array boundaries, so we need to limit it to N-1. This means subarray from (0, 7) indexes will be compared with subarray (8, 9).

Trace — Top-down Vs Bottom-up Mergesort

Top-down Vs Bottom-up Mergesort —algs4.cs.princeton.edu

Analysis

Time → Same as “top-down” Mergesort; It takes a total cost of O(N LogN). The outer loop doubles the size every time(multiplies by 2), while the inner loop takes O(N).
Memory → Same as “top-down” Mergesort; It uses extra space for the aux[] array.

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.