Part of course:

Merge-sort: Video tutorial, pseudo-code and run-time analysis

- Merge-sort Algorithm
- GIF animation of Merge-sort
- Algorithm Steps
- Run-time analysis
- Code (almost python)
- References

NaN.

Part of course: Competitive Programming: From Beginner to Expert

Merge-sort: Video tutorial, pseudo-code and run-time analysis[ Edit ]

We want to sort an array with n elements. Merge-sort does this by breaking up the array into two-halves, sorting them separately and then combining the results.

The first 2.5 minutes of the video above explain the merge-sort algorithm. The next 3 minutes (optional) compare merge-sort and quick-sort in one case where quick-sort's pivot choices get lucky, and another where quick-sort gets unlucky.

define mergesort(x):recursively sort first-half of xrecursively sort second-half of xmerge sorted halfs into single sorted array

The easiest way to understand the run-time complexity of merge-sort is to ** look** at the recursion graph. There are O(

define mergesort(x):""" Sort array using merge sort algorithm """# base caseif length(x) <= 1: return x# split from middle. mergesort each half. then mergemiddle = length(x)/2a = mergesort(x[:middle])b = mergesort(x[middle:])return merge(a, b)define merge(a, b):""" merge arrays a and b """c = list()while not empty(a) or not empty(b):# add smaller element to c and remove from original array# (handle boundary cases of a / b being empty)if empty(a) or (not empty(b) and a[0] <= b[0]):c.append(a[0])a.pop()else:c.append(b[0])b.pop()return c

Read more…(179 words)

Mark as completed

Previous

[ZCO12002] Wormholes (ZCO 2012: India)

Next

[INOI1201] Triathlon (INOI 2012: India)

Part of courses:

About the contributor:

Keshav DhandhaniaIOI medalist. DM me for 1-on-1 mentorship (paid).

100%

Loading…

Have a question? Ask here…

Post

Part of course:

Merge-sort: Video tutorial, pseudo-code and run-time analysis

- Merge-sort Algorithm
- GIF animation of Merge-sort
- Algorithm Steps
- Run-time analysis
- Code (almost python)
- References

Ready to join our community?

Sign up below to automatically get notified of new courses, get **reminders** to finish ones you subscribe to, and **bookmark** lessons to read later.

Continue with Facebook

— OR —

Your Full Name

Email address

I have an account. Log in instead

By signing up, you agree to our Terms and our Privacy Policy.

Popular Courses

New Courses

About Us

Get in touch

Copyright 2016-18, Compose Labs Inc. All rights reserved.