Day 37/100 Mergesort

Today I continued with the coursera course and studied Mergesort. Below are some of the notes I’ve taken:

Mergesort:

Typical workflow of mergesort algorithm

Mergesort is a typical divide and conquer algorithm. It takes a problem, divides into smaller versions of the problem, solves those smaller versions and merges solutions back together. The basic description of Mergesort is described as dividing an array into two halves then recursively sorting each half and merging final two halves. Usually 3 indices maintained to iterator through left sorted array, right sorted array and final sorted array. Big O complexity given as the following:

• Sorting Analysis: Time — NlogN , Space — 6NlgN array accesses, Compares — ∼(1/2)​nlog2​n (BEST),

Efficency:

In order to improve runtime of mergesort, implement a few changes:

• Use insertion sort if items to sort less than 7. This makes it around 20% faster!
• For 2 sorted arrays, check if biggest item in the first array is smaller than smallest item in second array = a[mid]≤a[mid+1]. This means it’s already sorted! Will reduce compares from ∼(1/2)​nlog2​n at best to n -1.
• Implement an in place (similar to insertion sort) Mergesort algorithm! This will reduce space complexity to a constant as standard implementation requires extra space proportional to N.

Bottom-up Mergesort:

No recursion!

Initially divides original array into N sized arrays then merges arrays and sorts by 2, 4, 8….N/2. At each level N checks are completed so complexity is same as top down approach of NlogN. This way is about 10% slower than recursive top down approach.

Additional notes :

• Look up useful discrete mathematics (what is ‘useful’ for sorting algorithms?).
• If two compare values are the same, always item from array on the left (Mergesort).
• Assert statements help detect logic bugs and documents code. Best practice as you can disable at run time (for production).