Как отсортировать на месте с помощью алгоритма сортировки слиянием?

Я знаю, что вопрос не слишком конкретен.

Все, что я хочу, это чтобы кто-то сказал мне, как преобразовать обычную сортировку слиянием в сортировку слиянием на месте (или сортировку слиянием с постоянными дополнительными пробелами).

Все, что я могу найти (в сети), это страницы с надписью «это слишком сложно» или «выходит за рамки этого текста».

Единственные известные способы слияния на месте (без какого-либо дополнительного пространства) слишком сложны, чтобы сводить их к практической программе. (взято отсюда )

Даже если это слишком сложно, какова основная концепция того, как сделать сортировку слиянием на месте?

Кнут оставил это как упражнение (Том 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 элемента, достаточно большой, чтобы объединить А и В? К сожалению, это не так.

Однако второе ограничение, упомянутое выше, дает нам подсказку, что мы можем использовать его, расположив рабочую область так, чтобы она перекрывалась с любым подмассивом, если мы сможем обеспечить последовательность слияния, чтобы не слитые элементы не были перезаписаны.

На самом деле, вместо сортировки второй половины рабочей области, мы можем отсортировать первую половину и поместить рабочую область между двумя отсортированными массивами следующим образом:

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

Эта установка эффективно организует перекрытие рабочей области с подмассивом A. Эта идея предложена в [Jyrki Katajainen, Tomi Pasanen, Jukka Teuhola. `` Практическая сортировка на месте ''. Nordic Journal of Computing, 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 определен ранее.

Полный исходный код можно найти здесь, а подробное объяснение можно найти здесь

Кстати, эта версия не самая быстрая сортировка слиянием, потому что она требует больше операций подкачки. Согласно моему тесту, это быстрее, чем стандартная версия, которая выделяет дополнительные пробелы в каждой рекурсии. Но это медленнее, чем оптимизированная версия, которая заранее удваивает исходный массив и использует его для дальнейшего слияния.

Включая свой «большой результат», эта статья описывает пару вариантов сортировки слиянием на месте (PDF):

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

Сортировка на месте с меньшим количеством ходов

Юрки Катаяйнен, Томи А. Пасанен

Показано, что массив из 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

Оптимальное стабильное слияние

Антониос Симвонис

В этой статье показано, как стабильно объединить две последовательности A и B размеров m и n, m ≤ n соответственно, с O (m + n) назначениями, O (mlog (n / m + 1)) сравнениями и используя только константу количество дополнительного места. Этот результат соответствует всем известным нижним границам ...

Это на самом деле не просто и не эффективно, и я предлагаю вам не делать этого, если вам действительно не нужно (и, вероятно, вам не нужно делать это, если это не домашняя работа, поскольку приложения слияния на месте в основном теоретические). Вы не можете использовать быструю сортировку вместо этого? Быстрая сортировка будет быстрее в любом случае с несколькими более простыми оптимизациями, и ее дополнительная память будет O (log N) .

Во всяком случае, если вы должны сделать это, то вы должны. Вот что я нашел: один и два . Я не знаком с сортировкой слиянием на месте, но кажется, что основная идея состоит в том, чтобы использовать ротации для облегчения объединения двух массивов без использования дополнительной памяти.

Обратите внимание, что это медленнее, чем классическая сортировка слиянием, которой нет на месте.

Критическим шагом является установление самого слияния . Это не так сложно, как видно из этих источников, но вы что-то теряете при попытке.

Глядя на один шаг слияния:

[... список отсортирован ... | x ... list- A ... | у ... список- Б ...]

Мы знаем , что отсортированная последовательность меньше , чем все остальное, что х меньше , чем все остальное в A , и что у меньше , чем все остальное в B . В случае, когда x меньше или равен y , вы просто перемещаете указатель на начало A на единицу. В случае, когда у меньше х , вы должны перетасовать у всей А для сортировки . Этот последний шаг - то, что делает это дорогим (кроме в вырожденных случаях).

Как правило, дешевле (особенно когда массивы на самом деле содержат только отдельные слова на элемент, например, указатель на строку или структуру), чтобы обменять некоторое пространство на время и иметь отдельный временный массив, который вы сортируете назад и вперед.

Просто для справки, вот хорошая реализация устойчивой сортировки слиянием на месте . Сложно, но не так уж плохо.

В итоге я реализовал как стабильную сортировку слиянием на месте, так и стабильную быструю сортировку на месте в Java. Обратите внимание, что сложность O (n (log n) ^ 2)

Пример слияния без буфера в 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);
}

Этот ответ имеет пример кода , который реализует алгоритм, описанный в статье Практическое слияние на месте Бинг-Чао Хуанга и Майкла А. Лэнгстона. Я должен признать, что я не понимаю деталей, но данная сложность шага слияния равна 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 ++, вероятно, переключатся на реализацию такого типа.

Это моя версия 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--;
    }
  }
}

Существует относительно простая реализация сортировки слиянием на месте с использованием оригинальной методики Kronrod, но с более простой реализацией. Наглядный пример, иллюстрирующий эту технику, можно найти здесь: http://www.logiccoder.com/TheSortProblem/BestMergeInfo.htm .

Есть также ссылки на более подробный теоретический анализ того же автора, связанный с этой ссылкой.

Я только что попробовал на месте алгоритм слияния для сортировки слиянием в JAVA , используя алгоритм сортировки вставкой, используя следующие шаги.
1) Два отсортированных массива доступны.
2) Сравните первые значения каждого массива; и поместите наименьшее значение в первый массив.
3) Поместите большее значение во второй массив, используя сортировку вставки (перемещение слева направо).
4) Затем снова сравните второе значение первого массива и первое значение второго массива и сделайте то же самое. Но когда происходит обмен, есть некоторая подсказка при пропуске, сравнивающая дальнейшие элементы, но требуется только обмен.

Я сделал некоторую оптимизацию здесь; держать меньшие сравнения в сортировке вставки.
Единственный недостаток, который я обнаружил в этом решении, заключается в том, что он требует большей замены элементов массива во втором массиве.

например)

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