Brian Yang
Brian Yang
algorithm designer
Mar 10, 2020 2 min read

Pseudocode for Mergesort

thumbnail for this post

Path from Comprehension to Implementation

The path to implementation is filled with gaps. It’s one thing to understand an algorithm. It’s another thing to be able to implement it. Often a course of learning explains the concept. The learner is left on their own, to implement this. Other factors make this more of a challenge. Nervousness, unfamiliarity, subtle changes to requirements, are some examples. The goal here is to provide you with tools to master implementation.

  1. explain the concept
  2. provide sample implementation
  3. provide a means for you to partially implement a solution, with clues
  4. full implementation from a blank slate

Video

Explanation

Input is an array of size n, while output is a sorted array of size n. Can we apply the Divide and Conquer paradigm to sorting?

Split the array, sort halves recursively, merge the result

mergesort(A, aux, lo, hi)
  if (hi-lo<=1) return 
  mid=(lo+hi)/2
  mergesort(A, lo, mid)
  mergesort(A, mid+1, hi)
  C=merge(A[lo:mid], A[mid+1:hi])
  copy elements from C back to A

Analysis

recurrence for merge sort: T(n)=2T(n⁄2)+O(n)

  • recursively sort but subarrays 2T(n⁄2)
  • merging requires 2n∈O(n)
  • base case T(1)=0

Telescoping

  • T(n)=2T(n⁄2)+n

  • T(n)=2(2T(n⁄4)+n⁄2)+n

  • T(n)=2kT(n⁄2k)+…+4n⁄4 + 2n⁄2 + n

  • remember n⁄2k=1 when k=lgn

  • we have lgn terms, each of the form 2k n⁄2k=n

  • total runtime of mergesort is ∈ O(n*lgn)

Takeaway: divide and conquer gives us a better algorithm for sorting

Sample Implementation

pseudo code

input: unsorted array
output: sorted array

divide and conquer

  • def base case
  • arr.length<2
  • def middle point
  • Math.floor(arr.lenght/2)
  • def left
  • arr.slice(0, middle)
  • def right
  • arr.slice(midde)
  • push left or right depending on which is greater
  • arr.push(left.shift())
  • concatenate left and right
  • left.slice().concat(right.slice())

Implement Partial Solution

input: [9, 2, 5, 6, 4, 3, 7, 10, 1, 8]
output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

write the code below

function merge(left, right) { // define empty arr // loop through args while () { // def loop condition // def condition if () { // push onto left (remember while loop conditional) } else { } } // concatenate } function mergeSort(arr) { // def base case // def vars (remember non-primitives are passed by reference) // pass recursively invoked left and right to merge fn } mergeSort([9, 2, 5, 6, 4, 3, 7, 10, 1, 8])
output:

Toggle Example Implementation

function merge(left, right) { let arr = []; while (left.length && right.length) { if (left[0] < right[0]) { arr.push(left.shift()); } else { arr.push(right.shift()); } } return arr.concat(left.slice().concat(right.slice())); } function mergeSort(arr) { if (arr.length < 2) return arr const middle = Math.floor(arr.length / 2); const left = arr.slice(0, middle); const right = arr.slice(middle); return merge(mergeSort(left), mergeSort(right)); } mergeSort([9, 2, 5, 6, 4, 3, 7, 10, 1, 8])

Implement Full Solution

function mergeSort(){ // write code here }
output:

references: PennX: SD3x, Algorithm Design and Analysis

    « Data Structure Diagrams Computer Science in 5 Minutes »
    comments powered by Disqus