Skip to content

Instantly share code, notes, and snippets.

@jcasimir

jcasimir/merge_sort.markdown

Last active November 7, 2018 18:47
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jcasimir/6fca38c58e5cc25594eace1d875210c8 to your computer and use it in GitHub Desktop.
Save jcasimir/6fca38c58e5cc25594eace1d875210c8 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
merge_sort.markdown

Merge Sort

Instructions

Complete these steps with roles Person 1 (P1) and Person 2 (P2):

  • P1 selects 5 of your numbers at random
  • P2 walks through the algorithm sorting those five numbers out loud to practice without counting steps
  • P1 adds three new cards, shuffles, and sorts the set out loud. P2 counts the steps using the guidelines below.
  • P2 adds two more cards, shuffles, and sorts the set out loud. P1 counts the steps using the guidelines below

Step Counting

Increment your number of steps for each of these operations:

  • Split a set into two
  • Compare two numbers
  • Move an element from one set to an output set

Algorithm

  1. Start with all your numbers laid out in a line (aka "collection") left to right
  2. If the collection has more than one element, split it into two similarly sized collections. Repeat Step 2 for each of the new collections until there are no collections left to split.
  3. Pick one collection at random and call it A and use the name current-A to refer to the first element of A.
  4. Pick a second collection and call it B and use the name current-B to refer to the first element of B.
  5. Compare current-A to current-B
  • If both are null, move to step 6
  • If only one is null, move the entire other collection to the output set and go to Step 3
  • If neither are null, move the smaller one to the output set, move the name (current-A or current-B) to point to the next element in it's list, and repeat Step 5
  1. If all collections have been combined into one, that's your output and you're done. If not, go to Step 4.

In the end you should have a single output collection.

Analysis

Discuss and write answers to these questions in your notebook:

  1. What would the worst case input set be for this algorithm? What would be the best?
  2. What parts of the process would happen even if the input was the best-case scenario?
  3. How would the number of operations grow as the number of inputs increases?
  4. How confidently could you implement Merge Sort in software?
  5. How does your answer to (4) affect your thinking on whether this is a "good" or "bad" algorithm?
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment