Merge Sort

Merge Sort

  • Complexity is O(n log n)
  • Needs more space to merge – proportional to the size of the array
  • Stable Sort
    • Preserves the order of equal elements
  • Merge Sort does about 39% lower comparisons, in worst case, compared to Quicksort’s average case
  • The algo almost always behaves in the same way; taking relatively the same amount of time, whether sorted or unsorted arrays

Testing Notes

  • Started testing the algo with two versions.
    • First version creates two temporary arrays
    • First version creates only one temporary array
  • The sole difference between them is the one that makes second implementation better

Code

As usual the code is available here:

https://github.com/abhi1010/Algorithms

Numbers

Merge Sort

# of Items in Array Time Taken Average for 100 numbers
Random 10 0.047464 0.47464
1K 5.41906 0.541906
1M 8444.11 0.844411
Sorted 10 0.027155 0.27155
1K 4.47016 0.447016
1M 6323.05 0.632305

Merge Sort 2

# of Items in Array Time Taken Average for 100 numbers
Random 10 0.033668 0.33668
1K 3.89374 0.389374
1M 7076.04 0.707604
Sorted 10 0.019034 0.19034
1K 2.7833 0.27833
1M 4664.16 0.466416
Advertisements

One thought on “Merge Sort

  1. Pingback: Heap Sort vs Merge Sort vs Insertion Sort vs Radix Sort vs Counting Sort vs Quick Sort |

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s