Merge Sort

DESCRIPTION

Merge Sort is a sorting algorithm based on the Divide et Impera technique, like Quick Sort. It can be implemented iteratively or recursively, using the Top-Down and Bottom-Up algorithms respectively. We represented the first one.

The algorithm divides the data structure recursively until the subsequences contain only one element. At this point, the subsequences get merged and ordered sequentially. To do so, the algorithm progressively builds the sorted sublist by adding each time the minimum element of the next two unsorted subsequences until there is only one sublist remaining. This will be the sorted data structure.

COMPLEXITY

Average Complexity | O(n × log n) |
---|---|

Best Case | O(n × log n) |

Worst Case | O(n × log n) |

Space Complexity | O(n) |