Merge sort in 3 minutes
Merge sort in 3 minutes
Step by step instructions showing how to run merge sort.
Code: https://github.com/msambol/dsa/blob/m… (different than video, I added this retroactively)
Sources:
1. Data Structures and Abstractions with Java by Frank M. Carrano [https://www.amazon.com/Structures-Abs…]
2. http://www.algorithmist.com/index.php…
LinkedIn: https://www.linkedin.com/in/michael-s…
Content
0.03 -> today we're going to learn mergesort a few
quick points then we'll get to the example
5.37 -> mergesort is usually done recursively
when you think of merge sort as with
11.31 -> other recursive algorithms I want you to
think of divide and conquer we're going
16.29 -> to break our problem into smaller problems
in order to solve it let's get started we
22.53 -> have the following array and we want it sorted
we're going to continuously split the array in
28.08 -> half our divide step until we are left
with the individual items watch and see
40.71 -> you
49.19 -> our arrays now broken down into individual
items one note before we start sorting when
57.08 -> you implement this in code these steps we done
in a different order because of recursion but
62.15 -> I think this human-friendly order provides more
clarity and learning let's continue we're ready
68.39 -> to sort will examine the individual items compare
their values and merge them into temporary arrays
82.1 -> you
93.3 -> the temporary rays are sorted but there's work
left to do let's jump up the recursion stack
99.81 -> and continue we merge our smaller arrays into a
larger one inserting items in the correct order
113.64 -> you
123.45 -> one more merge and we'll have our sorted array
132.97 -> you
137.81 -> and that's it our array is now
sorted here's the pseudocode
143.54 -> for merge sort on the left you have
the recursive part which halves the
148.43 -> arrays on the right is the merge
function which combines the arrays
153.82 -> mergesort has a worst case time complexity of Big
O of n times log in the easiest way to think about
161.17 -> it is to start with the merge step looking at the
while loop we see we have to visit n items the log
168.37 -> n comes from the maximum height of a binary tree
we create which is on the order of log N thank you
176.09 -> for watching please comment suggestions for future
videos below as well as any questions you may have
Source: https://www.youtube.com/watch?v=4VqmGXwpLqc