In place merge sort

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “In-place Merge Sort”.

1. Merge sort uses which of the following algorithm to implement sorting?
a) backtracking
b) greedy algorithm
c) divide and conquer
d) dynamic programming
View Answer

2. What is the average case time complexity of standard merge sort?
a) O(n log n)
b) O(n 2 )
c) O(n 2 log n)
d) O(n log n 2 )
View Answer

3. What is the auxiliary space complexity of standard merge sort?
a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)
View Answer

4. What is the space complexity of in place merge sort?
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
View Answer

5. What is the average time complexity of in place merge sort when we use the following function for merging?

a) O(n log n)
b) O(n 2 )
c) O(n 2 log n)
d) O(n log n 2 )
View Answer

6. Merge sort uses which of the following method to implement sorting?
a) merging
b) partitioning
c) selection
d) exchanging
View Answer

7. In place merge sort has same time complexity as standard merge sort.
a) true
b) false
View Answer

8. In-place merge sort is a stable sort.
a) true
b) false
View Answer

9. Choose the incorrect statement about merge sort from the following?
a) both standard merge sort and in-place merge sort are stable
b) standard merge sort has greater time complexity than in-place merge sort
c) standard merge sort has greater space complexity than in-place merge sort
d) in place merge sort has O(log n) space complexity
View Answer

10. Choose the correct function from the following that implements merging in in-place merge sort.
a)

Читайте также:  Гриль духовка барбекю redmond

I know the question is not too specific.

All I want is someone to tell me how to convert a normal merge sort into an in-place merge sort (or a merge sort with constant extra space overhead).

All I can find (on the net) is pages saying "it is too complex" or "out of scope of this text".

The only known ways to merge in-place (without any extra space) are too complex to be reduced to practical program. (taken from here)

Even if it is too complex, what is the basic concept of how to make the merge sort in-place?

10 Answers 10

Knuth left this as an exercise (Vol 3, 5.2.5). There do exist in-place merge sorts. They must be implemented carefully.

First, naive in-place merge such as described here isn’t the right solution. It downgrades the performance to O(N 2 ).

The idea is to sort part of the array while using the rest as working area for merging.

For example like the following merge function.

It takes the array xs , the two sorted sub-arrays are represented as ranges [i, m) and [j, n) respectively. The working area starts from w . Compare with the standard merge algorithm given in most textbooks, this one exchanges the contents between the sorted sub-array and the working area. As the result, the previous working area contains the merged sorted elements, while the previous elements stored in the working area are moved to the two sub-arrays.

However, there are two constraints that must be satisfied:

  1. The work area should be within the bounds of the array. In other words, it should be big enough to hold elements exchanged in without causing any out-of-bound error.
  2. The work area can be overlapped with either of the two sorted arrays; however, it must ensure that none of the unmerged elements are overwritten.
Читайте также:  Как вставить дополнительную строку в excel

With this merging algorithm defined, it’s easy to imagine a solution, which can sort half of the array; The next question is, how to deal with the rest of the unsorted part stored in work area as shown below:

One intuitive idea is to recursive sort another half of the working area, thus there are only 1/4 elements haven’t been sorted yet.

The key point at this stage is that we must merge the sorted 1/4 elements B with the sorted 1/2 elements A sooner or later.

Is the working area left, which only holds 1/4 elements, big enough to merge A and B? Unfortunately, it isn’t.

However, the second constraint mentioned above gives us a hint, that we can exploit it by arranging the working area to overlap with either sub-array if we can ensure the merging sequence that the unmerged elements won’t be overwritten.

Actually, instead of sorting the second half of the working area, we can sort the first half, and put the working area between the two sorted arrays like this:

This setup effectively arranges the work area overlap with the sub-array A. This idea is proposed in [Jyrki Katajainen, Tomi Pasanen, Jukka Teuhola. “Practical in-place mergesort”. Nordic Journal of Computing, 1996].

So the only thing left is to repeat the above step, which reduces the working area from 1/2, 1/4, 1/8, … When the working area becomes small enough (for example, only two elements left), we can switch to a trivial insertion sort to end this algorithm.

Here is the implementation in ANSI C based on this paper.

Читайте также:  Как перейти на другой тариф мгтс

Where wmerge is defined previously.

The full source code can be found here and the detailed explanation can be found here

By the way, this version isn’t the fastest merge sort because it needs more swap operations. According to my test, it’s faster than the standard version, which allocates extra spaces in every recursion. But it’s slower than the optimized version, which doubles the original array in advance and uses it for further merging.

Implement Merge Sort i.e. standard implementation keeping the sorting algorithm as in-place.
In-place means it does not occupy extra memory for merge operation as in standard case.

Examples:

Input: arr[] = <2, 3, 4, 1>
Output: 1 2 3 4

Input: arr[] = <56, 2, 45>
Output: 2 45 56

Recommended: Please try your approach on first, before moving on to the solution.

Approach:

  • Maintain two pointers which point to start of the segments which have to be merged.
  • Compare the elements at which the pointers are present.
  • If element1 filter_none

Note : Time Complexity of above approach is O(n 2 Log n) because merge is O(n 2 ). Time complexity of standard merge sort is less, O(n Log n).

Recommended Posts:

If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please Improve this article if you find anything incorrect by clicking on the "Improve Article" button below.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Adblock detector