The Bible of Algorithms and Data Structures: A Complex Subject Simply Explained (Runtime Complexity, Big O Notation, Programming) by Dedov Florian

Author:Dedov, Florian [Dedov, Florian]
Language: eng
Format: epub
Publisher: UNKNOWN
Published: 2020-08-19T16:00:00+00:00

Fig. 4.2: Merge sort dividing

What you can see in the figure above is the first part of the process, namely the division. We start out with an unsorted list and split it up recursively afterwards. We do this until we only have single elements to process. Then we can start merging.

Fig. 4.3: Merge sort merging

The process of merging is actually quite simple. Since all the sub-lists (in the beginning those of length one) are already sorted, all we need to do is to compare the smallest element of the one list to the smallest element of the other list and pick the smaller one. When we have the two sub-lists 3-5-6-7 and 1-2-4 for example, all we need to do is to compare one and three, since the two lists are sorted and there cannot be any smaller numbers. After we have chosen one, we continue by comparing two and three, then four and three and so on, until we end up with a larger combined sorted list.

So in a nutshell it is just splitting up a large list into its individual elements and then combining them into a sorted list step-by-step afterwards. Even though it is pretty easy to understand, the code for this algorithm is quite extensive and analyzing it would be unnecessarily time-consuming. Furthermore, since the main focus of this book is not to constantly analyze algorithms (we did quite a lot of this already), we will determine the runtime complexity of this algorithm, using logical thinking and intuition.

Essentially merge sort can be summarized in three steps:

1. Dividing the given list into sub-lists

2. Recursive call for sorting

3. Merging the results

Dividing the list can be done in constant time, so we can ignore this step for now. Merging the results is done in linear time, since we need to merge n elements. So because of step three, we already have at least linear time. But now the question is: How many times do we need to merge? For this we can look at step two. We are halving the problem size with each recursion. When you look at Fig. 4.2 again, you can see that we have n individual elements to merge. Merging happens in linear time and we need to merge n times. However, the problem size is one, which means that we need n operations for the first level of merging (ignoring constants). After that, we have four sorted sub-lists, which means we need to merge four times. But again the problem size is not n . It is n divided by four (except for the single element on the right). So roughly speaking we need to merge four times and the problem size is n divided by four. Thus we have n operations at this level as well. After that we end up with two sub-lists that are sorted. This again means that we need to merge two lists that are half the size of n . The factor two disappears and we have n operations once more.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.