Category Archives: Merge Sort

Merge Sort

Algorithm Video:

Merge Sort Combines Two Sorted file in a large bigger sorted files:
This Merge sort happens in a two steps:

This sorting is a example of divide and conquer approach:
1. Selection: Splits a list into two lists (This process is recursive approach)
2. Merging: It joins two list in a one list (It follows the pesudocode in itertive manner)

Pseudocode:

 

Implementation:
code with extra malloc declaration:

code by me without  extra malloc:

output:

Analysis of Running Time Complexity:

Worst case, Best case, Avergae case: Theta(nlogn)
Space Complexity: Theta(n)

 

This link can help to solve problems:
https://gist.github.com/mycodeschool/9678029
https://www.hackerearth.com/practice/algorithms/sorting/merge-sort/tutorial/

http://www.sanfoundry.com/cpp-program-implement-merge-sort/