Merge Sort

More notes coming soon!

  • We also can sort by merging. Merge sort is defined as follows:

    • Sort the left half.

    • Sort the right half.

    • Merge the sorted halves.

    To sort the left half, we’ll again ask the merge sort to help us. It will keep splitting the sorting problem into two until its size becomes 1. Then it will begin merging.

Example

Complexity

  • Merge sort takes Θ(NlogN)\Theta(N \log N) time and uses Θ(N)\Theta(N) memory.

Visualization

results matching ""

    No results matching ""