如何使用归并排序算法进行排序?

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?

即使它太复杂了，如何使归并排序的基本概念是什么?

9 个解决方案

#1

Knuth left this as an exercise (Vol 3, 5.2.5). There do exists in-place merge sort. It must be implemented carefully.

Knuth将此作为练习(Vol 3, 5.2.5)。存在就地归并排序。必须认真执行。

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

首先，这里描述的简单的就地合并不是正确的解决方案。它将性能降低到O(N2)。

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

其思想是将数组的一部分进行排序，而将其余部分用作合并工作区域。

For example as the following merge function.

例如以下合并函数。

void wmerge(Key* xs, int i, int m, int j, int n, int w) {
    while (i < m && j < n)
        swap(xs, w++, xs[i] < xs[j] ? i++ : j++);
    while (i < m)
        swap(xs, w++, i++);
    while (j < n)
        swap(xs, w++, j++);
}  

It takes the array xs, the two sorted sub arrays are represented as range [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 working area are moved to the two sub arrays.

它采用数组xs，两个有序的子数组分别表示为range [i, m]和[j, n)。工作区域从w开始，与大多数教科书中给出的标准归并算法相比，这一次交换了分类子数组和工作区域之间的内容。因此，前面的工作区域包含合并的排序元素，而在工作区中存储的前一个元素被移动到两个子数组中。

However, there are two constrains must be satisfied:

然而，有两个约束必须满足:

1. The work area should be within the bound of the array. In other words, it should be big enough to hold elements exchanged in without causing any out-of-bound error;
2. 工作区域应该在数组的范围内。换句话说，它应该足够大，能够在不引起任何超出范围的错误的情况下保存所交换的元素;
3. The work area can be overlapped with either of the two sorted arrays, however, it should be ensured that there are not any unmerged elements being overwritten;
4. 工作区域可以与两个排序的数组中的任意一个重叠，但是，应该确保没有任何未合并的元素被覆盖;

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 unsort part stored in work area as shown below:

通过这个合并算法的定义，很容易想到一个解决方案，它可以对数组的一半进行排序;下一个问题是，如何处理存储在工作区域的剩余部分，如下所示:

... unsorted 1/2 array ... | ... sorted 1/2 array ...

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.

一个直观的想法是递归排序工作区域的另外一半，因此只有1/4的元素还没有排序。

... unsorted 1/4 array ... | sorted 1/4 array B | sorted 1/2 array A ...

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.

这个阶段的关键点是，我们必须将已排序的1/4元素B和已排序的1/2元素合并在一起。

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

左边的工作区域只保留1/4的元素，大到可以合并A和B吗?不幸的是,它不是。

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:

实际上，我们不能对工作区域的下半部分进行排序，我们可以对前半部分进行排序，并将工作区域放在两个排序的数组之间:

... sorted 1/4 array B | unsorted work area | ... sorted 1/2 array A ...

This setup effects arrange 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].

这一设置影响了工作区域与子数组a的重叠。这个想法是在[Jyrki Katajainen, Tomi Pasanen, Jukka Teuhola]中提出的。“实际就地归并排序”。《北欧计算杂志》，1996年。

So the only thing left is to repeat the above step, which reduce 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.

所以剩下的就是重复上面的步骤，把工作区域从1/2减少到1/4,1/8…当工作区域变得足够小的时候，例如，只剩下两个元素，我们可以切换到一个简单的插入排序来结束这个算法。

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

这是基于本文的ANSI C的实现。

void imsort(Key* xs, int l, int u);

void swap(Key* xs, int i, int j) {
    Key tmp = xs[i]; xs[i] = xs[j]; xs[j] = tmp;
}

/* 
 * sort xs[l, u), and put result to working area w. 
 * constraint, len(w) == u - l
 */
void wsort(Key* xs, int l, int u, int w) {
    int m;
    if (u - l > 1) {
        m = l + (u - l) / 2;
        imsort(xs, l, m);
        imsort(xs, m, u);
        wmerge(xs, l, m, m, u, w);
    }
    else
        while (l < u)
            swap(xs, l++, w++);
}

void imsort(Key* xs, int l, int u) {
    int m, n, w;
    if (u - l > 1) {
        m = l + (u - l) / 2;
        w = l + u - m;
        wsort(xs, l, m, w); /* the last half contains sorted elements */
        while (w - l > 2) {
            n = w;
            w = l + (n - l + 1) / 2;
            wsort(xs, w, n, l);  /* the first half of the previous working area contains sorted elements */
            wmerge(xs, l, l + n - w, n, u, w);
        }
        for (n = w; n > l; --n) /*switch to insertion sort*/
            for (m = n; m < u && xs[m] < xs[m-1]; ++m)
                swap(xs, m, m - 1);
    }
}

Where wmerge is defined previously.

在前面定义了wmerge。

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.

顺便说一下，这个版本不是最快的归并排序，因为它需要更多的交换操作。根据我的测试，它比标准版本更快，它在每个递归中分配额外的空间。但是它比优化后的版本要慢，它会提前使原始数组加倍，并使用它进行进一步的合并。

#2

Including its "big result", this paper describes a couple of variants of in-place merge sort (PDF):

包括它的“大结果”，本文描述了几种in-place归并排序的变体(PDF):

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.5514&rep=rep1&type=pdf

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.5514&rep=rep1&type=pdf

In-place sorting with fewer moves

使用更少的移动的就地排序。

Jyrki Katajainen, Tomi A. Pasanen

Jyrki Katajainen, Tomi A. Pasanen。

It is shown that an array of n elements can be sorted using O(1) extra space, O(n log n / log log n) element moves, and n log 2 n+O(n log log n) comparisons. This is the first in-place sorting algorithm requiring o(n log n) moves in the worst case while guaranteeing O(n log n) comparisons, but due to the constant factors involved the algorithm is predominantly of theoretical interest.

它表明，n个元素的数组可以用O(1)额外空间，O(n log n / log n)元素移动，n log 2 n+O(n log log n)比较。这是第一个要求o(n log n)在最坏情况下移动的排序算法，同时保证o(n log n)的比较，但由于涉及的常数因素，算法主要是理论上的兴趣。

I think this is relevant too. I have a printout of it lying around, passed on to me by a colleague, but I haven't read it. It seems to cover basic theory, but I'm not familiar enough with the topic to judge how comprehensively:

我认为这也是相关的。我有一份打印出来的文件，是同事发给我的，但我没有读过。它似乎涵盖了基本理论，但我对这个主题还不够熟悉，无法全面判断:

http://comjnl.oxfordjournals.org/cgi/content/abstract/38/8/681

http://comjnl.oxfordjournals.org/cgi/content/abstract/38/8/681

Optimal Stable Merging

最优稳定合并

Antonios Symvonis

安东尼奥Symvonis

This paper shows how to stably merge two sequences A and B of sizes m and n, m ≤ n, respectively, with O(m+n) assignments, O(mlog(n/m+1)) comparisons and using only a constant amount of additional space. This result matches all known lower bounds...

本文展示了如何稳定地将m和n的两个序列A和B合并，分别用O(m+n)赋值，O(mlog(n/m+1))进行比较，只使用一个常数的额外空间。这个结果匹配所有已知的下界…

#3

The critical step is getting the merge itself to be in-place. It's not as difficult as those sources make out, but you lose something when you try.

关键的一步是让合并本身就位。这并不像那些消息来源说的那么难，但是当你尝试的时候你会失去一些东西。

Looking at one step of the merge:

看看合并的一个步骤:

[...list-sorted...|x...list-A...|y...list-B...]

[…list-sorted…| x列表…| y…发行b…]

We know that the sorted sequence is less than everything else, that x is less than everything else in A, and that y is less than everything else in B. In the case where x is less than or equal to y, you just move your pointer to the start of A on one. In the case where y is less than x, you've got to shuffle y past the whole of A to sorted. That last step is what makes this expensive (except in degenerate cases).

我们知道排序序列是不到一切,x小于其他,,y小于其他b的情况下x小于或等于y,你只要把你的指针的开始。在y小于x的情况下，你需要把y拖过整个A来排序。最后一步是使这个代价昂贵的原因(在退化的情况下除外)。

It's generally cheaper (especially when the arrays only actually contain single words per element, e.g., a pointer to a string or structure) to trade off some space for time and have a separate temporary array that you sort back and forth between.

它通常更便宜(特别是当数组只包含每个元素的单个单词时，例如，一个指向字符串或结构的指针)，以交换一些时间空间，并有一个单独的临时数组，您可以在它们之间来回排序。

#4

It really isn't easy or efficient, and I suggest you don't do it unless you really have to (and you probably don't have to unless this is homework since the applications of inplace merging are mostly theoretical). Can't you use quicksort instead? Quicksort will be faster anyway with a few simpler optimizations and its extra memory is O(log N).

这真的很不容易，也不是很有效，我建议你不要这样做，除非你真的必须这样做(你可能不需要这样做，除非这是家庭作业，因为inplace合并的应用大多是理论上的)。你不能用quicksort代替吗?无论如何，快速排序的速度将会更快，而且会有一些简单的优化，而它的额外内存是O(log N)。

Anyway, if you must do it then you must. Here's what I found: one and two. I'm not familiar with the inplace merge sort, but it seems like the basic idea is to use rotations to facilitate merging two arrays without using extra memory.

无论如何，如果你必须这样做的话，你必须这样做。这是我的发现:1和2。我不熟悉inplace归并排序，但它的基本思想是使用旋转来简化两个数组，而不需要额外的内存。

Note that this is slower even than the classic merge sort that's not inplace.

注意，这比传统的合并排序要慢一些。

#5

Just for reference, here is a nice implementation of a stable in-place merge sort. Complicated, but not too bad.

仅供参考，这里是一个稳定的就地合并排序的良好实现。很复杂，但还不算太糟。

I ended up implementing both a stable in-place merge sort and a stable in-place quicksort in Java. Please note the complexity is O(n (log n)^2)

我最终实现了一个稳定的就地归并排序和Java中稳定的就地快速排序。请注意复杂度是O(n(O(log n))^ 2)

#6

An example of bufferless mergesort in C.

#define SWAP(type, a, b) \
    do { type t=(a);(a)=(b);(b)=t; } while (0)

static void reverse_(int* a, int* b)
{
    for ( --b; a < b; a++, b-- )
       SWAP(int, *a, *b);
}
static int* rotate_(int* a, int* b, int* c)
/* swap the sequence [a,b) with [b,c). */
{
    if (a != b && b != c)
     {
       reverse_(a, b);
       reverse_(b, c);
       reverse_(a, c);
     }
    return a + (c - b);
}

static int* lower_bound_(int* a, int* b, const int key)
/* find first element not less than @p key in sorted sequence or end of
 * sequence (@p b) if not found. */
{
    int i;
    for ( i = b-a; i != 0; i /= 2 )
     {
       int* mid = a + i/2;
       if (*mid < key)
          a = mid + 1, i--;
     }
    return a;
}
static int* upper_bound_(int* a, int* b, const int key)
/* find first element greater than @p key in sorted sequence or end of
 * sequence (@p b) if not found. */
{
    int i;
    for ( i = b-a; i != 0; i /= 2 )
     {
       int* mid = a + i/2;
       if (*mid <= key)
          a = mid + 1, i--;
     }
    return a;
}

static void ip_merge_(int* a, int* b, int* c)
/* inplace merge. */
{
    int n1 = b - a;
    int n2 = c - b;

    if (n1 == 0 || n2 == 0)
       return;
    if (n1 == 1 && n2 == 1)
     {
       if (*b < *a)
          SWAP(int, *a, *b);
     }
    else
     {
       int* p, * q;

       if (n1 <= n2)
          p = upper_bound_(a, b, *(q = b+n2/2));
       else
          q = lower_bound_(b, c, *(p = a+n1/2));
       b = rotate_(p, b, q);

       ip_merge_(a, p, b);
       ip_merge_(b, q, c);
     }
}

void mergesort(int* v, int n)
{
    if (n > 1)
     {
       int h = n/2;
       mergesort(v, h); mergesort(v+h, n-h);
       ip_merge_(v, v+h, v+n);
     }
}

An example of adaptive mergesort (optimized).

Adds support code and modifications to accelerate the merge when an auxiliary buffer of any size is available (still works without additional memory). Uses forward and backward merging, ring rotation, small sequence merging and sorting, and iterative mergesort.

添加支持代码和修改，以加速合并时，任何大小的辅助缓冲区都可用(仍然可以工作而不需要额外内存)。使用前向和向后合并、环旋转、小序列合并和排序以及迭代归并排序。

#include <stdlib.h>
#include <string.h>

static int* copy_(const int* a, const int* b, int* out)
{
    int count = b - a;
    if (a != out)
       memcpy(out, a, count*sizeof(int));
    return out + count;
}
static int* copy_backward_(const int* a, const int* b, int* out)
{
    int count = b - a;
    if (b != out)
       memmove(out - count, a, count*sizeof(int));
    return out - count;
}

static int* merge_(const int* a1, const int* b1, const int* a2,
  const int* b2, int* out)
{
    while ( a1 != b1 && a2 != b2 )
       *out++ = (*a1 <= *a2) ? *a1++ : *a2++;
    return copy_(a2, b2, copy_(a1, b1, out));
}
static int* merge_backward_(const int* a1, const int* b1,
  const int* a2, const int* b2, int* out)
{
    while ( a1 != b1 && a2 != b2 )
       *--out = (*(b1-1) > *(b2-1)) ? *--b1 : *--b2;
    return copy_backward_(a1, b1, copy_backward_(a2, b2, out));
}

static unsigned int gcd_(unsigned int m, unsigned int n)
{
    while ( n != 0 )
     {
       unsigned int t = m % n;
       m = n;
       n = t;
     }
    return m;
}
static void rotate_inner_(const int length, const int stride,
  int* first, int* last)
{
    int* p, * next = first, x = *first;
    while ( 1 )
     {
       p = next;
       if ((next += stride) >= last)
          next -= length;
       if (next == first)
          break;
       *p = *next;
     }
    *p = x;
}
static int* rotate_(int* a, int* b, int* c)
/* swap the sequence [a,b) with [b,c). */
{
    if (a != b && b != c)
     {
       int n1 = c - a;
       int n2 = b - a;

       int* i = a;
       int* j = a + gcd_(n1, n2);

       for ( ; i != j; i++ )
          rotate_inner_(n1, n2, i, c);
     }
    return a + (c - b);
}

static void ip_merge_small_(int* a, int* b, int* c)
/* inplace merge.
 * @note faster for small sequences. */
{
    while ( a != b && b != c )
       if (*a <= *b)
          a++;
       else
        {
          int* p = b+1;
          while ( p != c && *p < *a )
             p++;
          rotate_(a, b, p);
          b = p;
        }
}
static void ip_merge_(int* a, int* b, int* c, int* t, const int ts)
/* inplace merge.
 * @note works with or without additional memory. */
{
    int n1 = b - a;
    int n2 = c - b;

    if (n1 <= n2 && n1 <= ts)
     {
       merge_(t, copy_(a, b, t), b, c, a);
     }
    else if (n2 <= ts)
     {
       merge_backward_(a, b, t, copy_(b, c, t), c);
     }
    /* merge without buffer. */
    else if (n1 + n2 < 48)
     {
       ip_merge_small_(a, b, c);
     }
    else
     {
       int* p, * q;

       if (n1 <= n2)
          p = upper_bound_(a, b, *(q = b+n2/2));
       else
          q = lower_bound_(b, c, *(p = a+n1/2));
       b = rotate_(p, b, q);

       ip_merge_(a, p, b, t, ts);
       ip_merge_(b, q, c, t, ts);
     }
}
static void ip_merge_chunk_(const int cs, int* a, int* b, int* t,
  const int ts)
{
    int* p = a + cs*2;
    for ( ; p <= b; a = p, p += cs*2 )
       ip_merge_(a, a+cs, p, t, ts);
    if (a+cs < b)
       ip_merge_(a, a+cs, b, t, ts);
}

static void smallsort_(int* a, int* b)
/* insertion sort.
 * @note any stable sort with low setup cost will do. */
{
    int* p, * q;
    for ( p = a+1; p < b; p++ )
     {
       int x = *p;
       for ( q = p; a < q && x < *(q-1); q-- )
          *q = *(q-1);
       *q = x;
     }
}
static void smallsort_chunk_(const int cs, int* a, int* b)
{
    int* p = a + cs;
    for ( ; p <= b; a = p, p += cs )
       smallsort_(a, p);
    smallsort_(a, b);
}

static void mergesort_lower_(int* v, int n, int* t, const int ts)
{
    int cs = 16;
    smallsort_chunk_(cs, v, v+n);
    for ( ; cs < n; cs *= 2 )
       ip_merge_chunk_(cs, v, v+n, t, ts);
}

static void* get_buffer_(int size, int* final)
{
    void* p = NULL;
    while ( size != 0 && (p = malloc(size)) == NULL )
       size /= 2;
    *final = size;
    return p;
}
void mergesort(int* v, int n)
{
    /* @note buffer size may be in the range [0,(n+1)/2]. */
    int request = (n+1)/2 * sizeof(int);
    int actual;
    int* t = (int*) get_buffer_(request, &actual);

    /* @note allocation failure okay. */
    int tsize = actual / sizeof(int);
    mergesort_lower_(v, n, t, tsize);
    free(t);
}

#7

This is my C version:

这是我的C版本:

void mergesort(int *a, int len) {
  int temp, listsize, xsize;

  for (listsize = 1; listsize <= len; listsize*=2) {
    for (int i = 0, j = listsize; (j+listsize) <= len; i += (listsize*2), j += (listsize*2)) {
      merge(& a[i], listsize, listsize);
    }
  }

  listsize /= 2;

  xsize = len % listsize;
  if (xsize > 1)
    mergesort(& a[len-xsize], xsize);

  merge(a, listsize, xsize);
}

void merge(int *a, int sizei, int sizej) {
  int temp;
  int ii = 0;
  int ji = sizei;
  int flength = sizei+sizej;

  for (int f = 0; f < (flength-1); f++) {
    if (sizei == 0 || sizej == 0)
      break;

    if (a[ii] < a[ji]) {
      ii++;
      sizei--;
    }
    else {
      temp = a[ji];

      for (int z = (ji-1); z >= ii; z--)
        a[z+1] = a[z];  
      ii++;

      a[f] = temp;

      ji++;
      sizej--;
    }
  }
}

#8

There is a relatively simple implementation of in-place merge sort using Kronrod's original technique but with simpler implementation. A pictorial example that illustrates this technique can be found here: http://www.logiccoder.com/TheSortProblem/BestMergeInfo.htm.

使用Kronrod的原始技术进行就地归并排序的实现相对简单，但实现起来更简单。可以在这里找到一个演示该技术的图形示例:http://www.logiccoder.com/TheSortProblem/BestMergeInfo.htm。

There are also links to more detailed theoretical analysis by the same author associated with this link.

与此链接相关的同一作者也有更详细的理论分析的链接。

#9

I just tried in place merge algorithm for merge sort in JAVA by using the insertion sort algorithm, using following steps.
1) Two sorted arrays are available.
2) Compare the first values of each array; and place the smallest value into the first array.
3) Place the larger value into the second array by using insertion sort (traverse from left to right).
4) Then again compare the second value of first array and first value of second array, and do the same. But when swapping happens there is some clue on skip comparing the further items, but just swapping required.

我用插入排序算法在JAVA中尝试了合并排序的归并排序算法，使用以下步骤。1)有两个有序数组。2)比较每个数组的第一个值;将最小值放到第一个数组中。3)使用插入排序(从左到右)将较大的值放入第二个数组中。4)然后再次比较第一个数组的第二个值和第二个数组的第一个值，并做相同的操作。但是，当交换发生时，有一些关于跳过比较其他项的线索，但是只需要进行交换。

I have made some optimization here; to keep lesser comparisons in insertion sort.
The only drawback i found with this solutions is it needs larger swapping of array elements in the second array.

我在这里做了一些优化;在插入排序中保持较小的比较。我发现这个解决方案的唯一缺点是它需要在第二个数组中更大的数组元素交换。

e.g)

如)

First___Array : 3, 7, 8, 9

First___Array: 3、7、8、9。

Second Array : 1, 2, 4, 5

第二组:1,2,4,5。

Then 7, 8, 9 makes the second array to swap(move left by one) all its elements by one each time to place himself in the last.

然后，7、8、9使第二个数组(左移一个)所有元素在最后一个位置进行交换。

So the assumption here is swapping items is negligible compare to comparing of two items.

所以这里的假设是交换项目可以忽略两个项目的比较。

https://github.com/skanagavelu/algorithams/blob/master/src/sorting/MergeSort.java

https://github.com/skanagavelu/algorithams/blob/master/src/sorting/MergeSort.java

package sorting;

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
    int[] array = { 5, 6, 10, 3, 9, 2, 12, 1, 8, 7 };
    mergeSort(array, 0, array.length -1);
    System.out.println(Arrays.toString(array));

    int[] array1 = {4, 7, 2};
    System.out.println(Arrays.toString(array1));
    mergeSort(array1, 0, array1.length -1);
    System.out.println(Arrays.toString(array1));
    System.out.println("\n\n");

    int[] array2 = {4, 7, 9};
    System.out.println(Arrays.toString(array2));
    mergeSort(array2, 0, array2.length -1);
    System.out.println(Arrays.toString(array2));
    System.out.println("\n\n");

    int[] array3 = {4, 7, 5};
    System.out.println(Arrays.toString(array3));
    mergeSort(array3, 0, array3.length -1);
    System.out.println(Arrays.toString(array3));
    System.out.println("\n\n");

    int[] array4 = {7, 4, 2};
    System.out.println(Arrays.toString(array4));
    mergeSort(array4, 0, array4.length -1);
    System.out.println(Arrays.toString(array4));
    System.out.println("\n\n");

    int[] array5 = {7, 4, 9};
    System.out.println(Arrays.toString(array5));
    mergeSort(array5, 0, array5.length -1);
    System.out.println(Arrays.toString(array5));
    System.out.println("\n\n");

    int[] array6 = {7, 4, 5};
    System.out.println(Arrays.toString(array6));
    mergeSort(array6, 0, array6.length -1);
    System.out.println(Arrays.toString(array6));
    System.out.println("\n\n");

    //Handling array of size two
    int[] array7 = {7, 4};
    System.out.println(Arrays.toString(array7));
    mergeSort(array7, 0, array7.length -1);
    System.out.println(Arrays.toString(array7));
    System.out.println("\n\n");

    int input1[] = {1};
    int input2[] = {4,2};
    int input3[] = {6,2,9};
    int input4[] = {6,-1,10,4,11,14,19,12,18};
    System.out.println(Arrays.toString(input1));
    mergeSort(input1, 0, input1.length-1);
    System.out.println(Arrays.toString(input1));
    System.out.println("\n\n");

    System.out.println(Arrays.toString(input2));
    mergeSort(input2, 0, input2.length-1);
    System.out.println(Arrays.toString(input2));
    System.out.println("\n\n");

    System.out.println(Arrays.toString(input3));
    mergeSort(input3, 0, input3.length-1);
    System.out.println(Arrays.toString(input3));
    System.out.println("\n\n");

    System.out.println(Arrays.toString(input4));
    mergeSort(input4, 0, input4.length-1);
    System.out.println(Arrays.toString(input4));
    System.out.println("\n\n");
}

private static void mergeSort(int[] array, int p, int r) {
    //Both below mid finding is fine.
    int mid = (r - p)/2 + p;
    int mid1 = (r + p)/2;
    if(mid != mid1) {
        System.out.println(" Mid is mismatching:" + mid + "/" + mid1+ "  for p:"+p+"  r:"+r);
    }

    if(p < r) {
        mergeSort(array, p, mid);
        mergeSort(array, mid+1, r);
//      merge(array, p, mid, r);
        inPlaceMerge(array, p, mid, r);
        }
    }

//Regular merge
private static void merge(int[] array, int p, int mid, int r) {
    int lengthOfLeftArray = mid - p + 1; // This is important to add +1.
    int lengthOfRightArray = r - mid;

    int[] left = new int[lengthOfLeftArray];
    int[] right = new int[lengthOfRightArray];

    for(int i = p, j = 0; i <= mid; ){
        left[j++] = array[i++];
    }

    for(int i = mid + 1, j = 0; i <= r; ){
        right[j++] = array[i++];
    }

    int i = 0, j = 0;
    for(; i < left.length && j < right.length; ) {
        if(left[i] < right[j]){
            array[p++] = left[i++];
        } else {
            array[p++] = right[j++];
        }
    }
    while(j < right.length){
        array[p++] = right[j++];
    } 
    while(i < left.length){
        array[p++] = left[i++];
    }
}

//InPlaceMerge no extra array
private static void inPlaceMerge(int[] array, int p, int mid, int r) {
    int secondArrayStart = mid+1;
    int prevPlaced = mid+1;
    int q = mid+1;
    while(p < mid+1 && q <= r){
        boolean swapped = false;
        if(array[p] > array[q]) {
            swap(array, p, q);
            swapped = true;
        }   
        if(q != secondArrayStart && array[p] > array[secondArrayStart]) {
            swap(array, p, secondArrayStart);
            swapped = true;
        }
        //Check swapped value is in right place of second sorted array
        if(swapped && secondArrayStart+1 <= r && array[secondArrayStart+1] < array[secondArrayStart]) {
            prevPlaced = placeInOrder(array, secondArrayStart, prevPlaced);
        }
        p++;
        if(q < r) {     //q+1 <= r) {
            q++;
        }
    }
}

private static int placeInOrder(int[] array, int secondArrayStart, int prevPlaced) {
    int i = secondArrayStart;
    for(; i < array.length; i++) {
        //Simply swap till the prevPlaced position
        if(secondArrayStart < prevPlaced) {
            swap(array, secondArrayStart, secondArrayStart+1);
            secondArrayStart++;
            continue;
        }
        if(array[i] < array[secondArrayStart]) {
            swap(array, i, secondArrayStart);
            secondArrayStart++;
        } else if(i != secondArrayStart && array[i] > array[secondArrayStart]){
            break;
        }
    }
    return secondArrayStart;
}

private static void swap(int[] array, int m, int n){
    int temp = array[m];
    array[m] = array[n];
    array[n] = temp;
}
}