Merge Sort

Creator

Creator

Created

Created

2020 Jan 10 12:51

Editor

Editor

Edited

Edited

2023 Sep 19 6:12

Refs

Refs

Divide and Conquer paradigm

Time

Time

O(n\;log\;n)

Worst

Worst

O(n\;log\;n)

Stable

Stable

Stable

Inplace

Inplace

Inplace

Comparision

Comparision

Comparision

T(n) = 2T(n/2) + \Theta(n)

2 means 2 sub problems

n/2 means subproblem size

$\Theta(n)$ means work dividing and combining

notion image

Practive

merge sort beats insertion sort for $n>30$

In computer science, merge sort is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the relative order of equal elements is the same in the input and output. Merge sort is a divide-and-conquer algorithm that was invented by John von Neumann in 1945. A detailed description and analysis of bottom-up merge sort appeared in a report by Goldstine and von Neumann as early as 1948.

https://en.wikipedia.org/wiki/Merge_sort

Merge sort

Recommendations

/////