如何使用合并排序算法进行就地排序？

Question

我知道这个问题不太具体。

我想要的只是有人告诉我如何将普通合并排序转换为就地合并排序（或具有恒定额外空间开销的合并排序）。

我（在网上）能找到的所有页面都写着“它太复杂”或“超出了本文的范围”。

唯一已知的就地合并（没有任何额外空间）的方法太复杂，无法简化为实际程序。 （取自此处）

即使它太复杂，如何就地进行合并排序的基本概念是什么？

Answer 1

Knuth 将此作为练习（第 3 卷，5.2.5）。确实存在就地合并排序。必须认真实施它们。

首先，天真的就地合并，如所述 这里不是正确的解决方案。它将性能降低至 O(N²)。

这个想法是对数组的一部分进行排序，同时使用其余部分作为合并的工作区域。

例如下面的合并函数。

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++);
}  

它采用数组xs，两个排序的子数组分别表示为范围[i, m)和[j, n)。工作区域从w开始。与大多数教科书中给出的标准合并算法相比，该算法在已排序的子数组和工作区之间交换内容。结果，前一个工作区包含合并后的排序元素，同时工作区中存储的前一个元素被移动到两个子数组中。

但是，必须满足两个约束：

1. 工作区域应该在数组的范围内。换句话说，它应该足够大，可以容纳交换的元素，而不会导致任何越界错误。
2. 工作区可以与两个排序数组中的任何一个重叠；但是，它必须确保未合并的元素不会被覆盖。

定义了这个合并算法后，很容易想象一个解决方案，它可以对数组的一半进行排序；接下来的问题是，如何处理工作区中剩余的未排序部分，如下所示：

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

一个直观的想法是对工作区的另一半​​进行递归排序，这样就只有 1/4 的元素没有排序然而。

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

这个阶段的关键点是我们必须合并已排序的1/4元素B
迟早会与已排序的 1/2 元素 A 一起使用。

工作区域是否剩余，仅容纳 1/4 元素，足够大以进行合并
A和B？不幸的是，事实并非如此。

然而，上面提到的第二个约束给了我们一个提示，如果我们能够确保合并顺序不会覆盖未合并的元素，我们可以通过将工作区域安排为与任一子数组重叠来利用它。

实际上，我们可以不对工作区域的后半部分进行排序，而是对前半部分进行排序，并将工作区域放在两个已排序的数组之间，如下所示：

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

这种设置有效地安排了工作区域与子数组 A 的重叠。
[Jyrki Katajainen、Tomi Pasanen、Jukka Teuhola] 中提出。 “实用的就地合并排序”。北欧计算杂志，1996]。

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

下面是基于本文的 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);
    }
}

其中 wmerge 是先前定义的。

完整的源代码可以在此处 详细说明可以在此处

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

Answer 2

包括其“大结果”，本文描述了就地合并排序的几个变体 (PDF)：

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

移动次数较少的就地排序

Jyrki Katajainen、Tomi A. Pasanen

表明n个数组
可以使用 O(1) 对元素进行排序
额外空间，O(n log n / log log n)
元素移动，n log₂n + O(n log
log n) 比较。这是第一个
就地排序算法需要
最坏情况下的移动次数为 o(n log n)
同时保证 O(n log n)
比较，但由于不断
算法涉及的因素是
主要是理论兴趣。

我认为这也是相关的。我手边有一份它的打印件，是一位同事传给我的，但我还没有读过。它似乎涵盖了基本理论，但我对该主题不够熟悉，无法判断其全面性：

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

最佳稳定合并

Antonios Symvonis

本文展示了如何稳定地合并
两个大小为 m 的序列 A 和 B
分别为 n、m ≤ n，其中 O(m+n)
分配，O(mlog(n/m+1))
比较并仅使用常数
额外空间量。这
结果匹配所有已知的下限...

Answer 3

这确实不容易或高效，我建议你不要这样做，除非你真的必须这样做（而且你可能不需要这样做，除非这是家庭作业，因为就地合并的应用大多是理论上的）。不能用快速排序来代替吗？无论如何，通过一些更简单的优化，快速排序会更快，并且它的额外内存是O(log N)。

无论如何，如果你必须这样做，那么你就必须这样做。这是我发现的： one 和 两个。我不熟悉就地合并排序，但似乎基本思想是使用旋转来促进合并两个数组而不使用额外的内存。

请注意，这甚至比非就地的经典合并排序还要慢。

Answer 4

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

查看合并的一个步骤：

[...列表-已排序...|x...列表-A...|y ...列表-B...]

我们知道排序序列小于其他所有内容，x小于所有内容A 中的 else ，并且 y 小于 B 中的其他所有内容。如果x小于或等于y，您只需将指针移动到A的开头。如果 y 小于 x，则必须将 y 洗牌到整个 A 排序。最后一步是导致成本高昂的原因（除非是退化的情况）。

通常，用一些空间换取时间并拥有一个可以在其之间来回排序的单独临时数组会更便宜（特别是当数组实际上每个元素仅包含单个单词时，例如，指向字符串或结构的指针）。

Answer 5

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);
     }
}

自适应归并排序（优化）的示例。

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

#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);
}

Answer 6

这个答案有一个代码示例，它实现了论文中描述的算法实用就地合并，作者：Bing-Chao Huang 和 Michael A. Langston。我不得不承认我不了解细节，但是给定的合并步骤的复杂度是 O(n)。

从实践的角度来看，有证据表明纯粹的就地实现在现实场景中并没有表现得更好。例如，C++ 标准定义了 std::inplace_merge，它是名称意味着就地合并操作。

假设 C++ 库通常经过很好的优化，看看它是如何实现的很有趣：

1) libstdc++（GCC 代码库的一部分）：std::inplace_merge

实现委托给 __inplace_merge，这就避免了这个问题尝试分配临时缓冲区：

typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
_TmpBuf __buf(__first, __len1 + __len2);

if (__buf.begin() == 0)
  std::__merge_without_buffer
    (__first, __middle, __last, __len1, __len2, __comp);
else
  std::__merge_adaptive
   (__first, __middle, __last, __len1, __len2, __buf.begin(),
     _DistanceType(__buf.size()), __comp);

否则，它将回退到实现（__merge_without_buffer)，不需要额外的内存，但不再以 O(n) 时间运行。

2) libc++ (Clang 代码库的一部分): std: :inplace_merge

看起来很相似。它委托给一个 函数，该函数还尝试分配缓冲区。根据是否获得足够的元素，它将选择实现。常量内存后备函数称为 __buffered_inplace_merge。

也许即使回退仍然是 O(n) 时间，但重点是，如果临时内存可用，他们不会使用该实现。

---

请注意，C++ 标准通过将所需的复杂性从 O(n) 降低到 O(N log N)，明确给予实现选择此方法的自由：

复杂性：
如果有足够的额外内存可用，则恰好进行 N-1 次比较。如果内存不足，则进行O(N log N)次比较。

当然，这不能证明永远不应该使用 O(n) 时间内的常量空间就地合并。另一方面，如果速度更快，优化的 C++ 库可能会切换到这种类型的实现。

Answer 7

这是我的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--;
    }
  }
}

Answer 8

我知道我迟到了，但这是我昨天写的解决方案。我也在其他地方发布了这个，但这似乎是 SO 上最流行的就地合并线程。我也没有在其他地方看到过这个算法，所以希望这对一些人有帮助。

该算法采用最简单的形式，以便于理解。可以对其进行显着调整以获得额外的速度。平均时间复杂度为：稳定就地数组合并为 O(n.log2n)，整体排序为 O(n.(log2n)2)。

//                     Stable Merge In Place Sort
//
//
// The following code is written to illustrate the base algorithm. A good
// number of optimizations can be applied to boost its overall speed
// For all its simplicity, it does still perform somewhat decently.
// Average case time complexity appears to be: O(n.(log₂n)²)

#include <stddef.h>
#include <stdio.h>

#define swap(x, y)    (t=(x), (x)=(y), (y)=t)

// Both sorted sub-arrays must be adjacent in 'a'
// Assumes that both 'an' and 'bn' are always non-zero
// 'an' is the length of the first sorted section in 'a', referred to as A
// 'bn' is the length of the second sorted section in 'a', referred to as B
static void
merge_inplace(int A[], size_t an, size_t bn)
{
    int t, *B = &A[an];
    size_t  pa, pb;     // Swap partition pointers within A and B

    // Find the portion to swap.  We're looking for how much from the
    // start of B can swap with the end of A, such that every element
    // in A is less than or equal to any element in B.  This is quite
    // simple when both sub-arrays come at us pre-sorted
    for(pa = an, pb = 0; pa>0 && pb<bn && B[pb] < A[pa-1]; pa--, pb++);

    // Now swap last part of A with first part of B according to the
    // indicies we found
    for (size_t index=pa; index < an; index++)
        swap(A[index], B[index-pa]);

    // Now merge the two sub-array pairings.  We need to check that either array
    // didn't wholly swap out the other and cause the remaining portion to be zero
    if (pa>0 && (an-pa)>0)
        merge_inplace(A, pa, an-pa);

    if (pb>0 && (bn-pb)>0)
        merge_inplace(B, pb, bn-pb);
} // merge_inplace

// Implements a recursive merge-sort algorithm with an optional
// insertion sort for when the splits get too small.  'n' must
// ALWAYS be 2 or more.  It enforces this when calling itself
static void
merge_sort(int a[], size_t n)
{
    size_t  m = n/2;

    // Sort first and second halves only if the target 'n' will be > 1
    if (m > 1)
        merge_sort(a, m);

    if ((n-m)>1)
        merge_sort(a+m, n-m);

    // Now merge the two sorted sub-arrays together. We know that since
    // n > 1, then both m and n-m MUST be non-zero, and so we will never
    // violate the condition of not passing in zero length sub-arrays
    merge_inplace(a, m, n-m);
} // merge_sort

// Print an array */
static void
print_array(int a[], size_t size)
{
    if (size > 0) {
        printf("%d", a[0]);
        for (size_t i = 1; i < size; i++)
            printf(" %d", a[i]);
    }
    printf("\n");
} // print_array
 
// Test driver
int
main()
{
    int a[] = { 17, 3, 16, 5, 14, 8, 10, 7, 15, 1, 13, 4, 9, 12, 11, 6, 2 };
    size_t  n = sizeof(a) / sizeof(a[0]);
 
    merge_sort(a, n);
 
    print_array(a, n);

    return 0;
} // main

Answer 9

利用 C++ std::inplace_merge，就地合并排序可以实现如下：

template< class _Type >
inline void merge_sort_inplace(_Type* src, size_t l, size_t r)
{
    if (r <= l) return;

    size_t m = l + ( r - l ) / 2;             // computes the average without overflow

    merge_sort_inplace(src, l,     m);
    merge_sort_inplace(src, m + 1, r);

    std::inplace_merge(src + l, src + m + 1, src + r + 1);
}

https://github.com/DragonSpit/ParallelAlgorithms 存储库，它是开源且免费的。

Answer 10

我刚刚尝试使用插入排序算法在 JAVA 中进行合并排序，具体步骤如下。
1) 有两个排序数组可用。
2）比较每个数组的第一个值；并将最小值放入第一个数组中。
3）使用插入排序（从左到右遍历）将较大的值放入第二个数组中。
4）然后再次比较第一个数组的第二个值和第二个数组的第一个值，并执行相同的操作。但是，当交换发生时，有一些线索可以跳过比较其他项目，但只需交换即可。

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

例如）

第一个数组：3,7,8,9

第二个数组：1,2,4,5

然后 7,8,9 使第二个数组每次将其所有元素交换（左移一位）以将自己放入最后一个。

因此，与比较两个项目相比，这里交换项目的假设可以忽略不计。

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;
}
}