Today we are going to look at merge sort<\/strong>.<\/p>\n Merge sort is a very efficient stable sorting algorithm that was invented in 1945 by John von Neumann, one of the pioneers in the field of computer science. It uses the divide and conquer technique, the basic idea is that if we have a complex problem we try to break it down into smaller parts and solve those parts separately. The final solution is therefore the result of solving each of the smaller sub-problems. Such a decomposition of problems can then be perfectly parallelized and solved efficiently on modern multi-core processors.<\/p>\n We divide the input data vector into several approximately equal parts. The most common version uses a 2-part partitioning, this is a binary merge, in the case of multiple parts it is a so-called K-way merge<\/a>. Let’s see how this technique can be used in data sorting.<\/p>\n The input data is divided into approximately two equal parts, if the number of elements is odd, the first part has 1 more element. Each of these parts of the array is further divided in half and this is repeated until the part contains only one element. This uses a recursive call. An array with one element is considered to be sorted. Once the parts can no longer be split, the last two halves are taken and their elements are merged so that the resulting list remains sorted as well. This is repeated until the original data vector is received in sorted form. This is best understood with the example in the following figure.<\/p>\n The merge sort animation looks like this:<\/p>\n Source: commons.wikimedia.org\/wiki\/Category:Animations_of_sort_algorithms<\/p>\n Visit Toptal <\/a> for interactive visualizations. There are 8 types of algorithms and you can also play the animation backwards.<\/p>\n On this page<\/a> you can go through the steps of the algorithm to check the time taken by the algorithm.<\/p>\nMerge sort meaning<\/h2>\n
How merge sort works<\/h2>\n
![\"Visual](\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/08\/algoritmus-merge-sortu-890-850.webp\")
Merge sort animation, visualization, gif<\/h2>\n
![\"CobaltBlue,](\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/08\/Merge_sort_animation2.gif\")
Merge sort algorithm advantages<\/h2>\n
\n
Merge sort algorithm disadvantages<\/h2>\n
\n
Merge sort time complexity<\/h2>\n
![\"Merge](\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/08\/vystup-z-prikladu-merge-sort-575-410-300x214.webp\")
<\/p>\n