# Merge Sort

Oct 6, 2012 · Commentscode 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 |