# The Angry Birds — Red

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

# 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 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:

- 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. - 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[]*. - 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.

## 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).*

**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 sortis 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 sortedaux[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++];

elseaux[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.

RememberAn 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

## 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.