Merge Sort

Oct 6, 2012 · Comments
code sortingalgoc++

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