Jak sortować w miejscu za pomocą algorytmu scalania?

Wiem, że pytanie nie jest zbyt szczegółowe.

Chcę tylko, żeby ktoś mi powiedział, jak przekonwertować normalny sortowanie scalające na sortowanie scalające na miejscu (lub sortowanie scalające ze stałym dodatkowym obszarem narzutu).

Wszystko, co mogę znaleźć (w sieci) to strony z napisem „jest zbyt skomplikowane” lub „poza zakresem tego tekstu”.

Jedyne znane sposoby łączenia na miejscu (bez dodatkowej przestrzeni) są zbyt skomplikowane, aby można je było zredukować do praktycznego programu. (wzięty stąd )

Nawet jeśli jest zbyt skomplikowana, jaka jest podstawowa koncepcja tego, jak scalić sortowanie na miejscu?

Knuth zostawił to jako ćwiczenie (tom 3, 5.2.5). Istnieją lokalne rodzaje scalania. Muszą być wdrażane ostrożnie.

Po pierwsze, naiwne scalanie w miejscu, takie jak opisane tutaj, nie jest właściwym rozwiązaniem. Obniża wydajność do O (N ² ) .

Chodzi o to, aby posortować część tablicy, a resztę wykorzystać jako obszar roboczy do scalenia.

Na przykład jak następująca funkcja scalania.

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

Potrzeba tablicę xs, obie tablice podrzędne sortowane są reprezentowane zakresie [i, m)i [j, n)odpowiednio. Obszar pracy zaczyna się od w. Porównaj ze standardowym algorytmem scalania podanym w większości podręczników, ten wymienia zawartość między posortowaną pod-tablicą a obszarem roboczym. W rezultacie poprzedni obszar roboczy zawiera scalone posortowane elementy, podczas gdy poprzednie elementy przechowywane w obszarze roboczym są przenoszone do dwóch pod-macierzy.

Istnieją jednak dwa ograniczenia, które należy spełnić:

1. Obszar roboczy powinien mieścić się w granicach tablicy. Innymi słowy, powinien być wystarczająco duży, aby pomieścić elementy wymieniane bez powodowania żadnego błędu spoza zakresu.
2. Obszar roboczy może się pokrywać z jednym z dwóch uporządkowanych zestawów; musi jednak zapewnić, że żaden z nie połączonych elementów nie zostanie nadpisany.

Po zdefiniowaniu tego algorytmu scalania łatwo jest wyobrazić sobie rozwiązanie, które może posortować połowę tablicy; Kolejne pytanie brzmi: jak postępować z resztą nieposortowanej części przechowywanej w obszarze roboczym, jak pokazano poniżej:

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

Intuicyjnym pomysłem jest sortowanie rekurencyjne innej połowy obszaru roboczego, dlatego jest tylko 1/4 elementów, które nie zostały jeszcze posortowane.

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

Kluczowym punktem na tym etapie jest to, że musimy scalić posortowane 1/4 elementów B z posortowanymi 1/2 elementami A prędzej czy później.

Czy pozostało miejsce do pracy, które mieści tylko 1/4 elementów, wystarczająco duże, aby połączyć A i B? Niestety tak nie jest.

Jednak drugie ograniczenie wspomniane powyżej daje nam wskazówkę, że możemy go wykorzystać, ustawiając obszar roboczy tak, aby zachodził na którąkolwiek z pod-macierzy, jeśli możemy zapewnić łączącą się sekwencję, że nie scalone elementy nie zostaną nadpisane.

W rzeczywistości zamiast sortować drugą połowę obszaru roboczego, możemy posortować pierwszą połowę i umieścić obszar roboczy między dwoma sortowanymi tablicami w następujący sposób:

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

Ta konfiguracja skutecznie rozmieszcza obszar roboczy pokrywający się z podobszarem A. Pomysł ten zaproponowano w [Jyrki Katajainen, Tomi Pasanen, Jukka Teuhola. `` Praktyczne połączenie w miejscu ''. Nordic Journal of Computing, 1996].

Pozostaje więc tylko powtórzyć powyższy krok, co zmniejsza obszar roboczy z 1/2, 1/4, 1/8,… Gdy obszar roboczy staje się wystarczająco mały (na przykład pozostały tylko dwa elementy), możemy przełącz się na trywialny sposób wstawiania, aby zakończyć ten algorytm.

Oto implementacja w ANSI C na podstawie tego dokumentu.

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

Gdzie wcześniej zdefiniowano wmerge.

Pełny kod źródłowy można znaleźć tutaj, a szczegółowe wyjaśnienie można znaleźć tutaj

Nawiasem mówiąc, ta wersja nie jest najszybszym sortowaniem scalającym, ponieważ wymaga więcej operacji wymiany. Według mojego testu jest on szybszy niż standardowa wersja, która przydziela dodatkowe miejsca w każdej rekurencji. Jest jednak wolniejszy niż wersja zoptymalizowana, która z góry podwaja pierwotną tablicę i wykorzystuje ją do dalszego łączenia.

Uwzględniając jego „duży wynik”, niniejszy artykuł opisuje kilka wariantów sortowania scalonego w miejscu (PDF):

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

Sortowanie na miejscu z mniejszą liczbą ruchów

Jyrki Katajainen, Tomi A. Pasanen

Pokazano, że tablicę n elementów można sortować za pomocą dodatkowej przestrzeni O (1), przesuwa się element O (n log n / log log n), a n log ₂ n + O (n log log n) porównania. Jest to pierwszy algorytm sortowania na miejscu, wymagający ruchów o (n log n) w najgorszym przypadku, przy jednoczesnym zagwarantowaniu porównań O (n log n), ale ze względu na stałe czynniki zaangażowany algorytm ma głównie znaczenie teoretyczne.

Myślę, że to też jest istotne. Mam na sobie wydruk, który przekazał mi kolega, ale go nie przeczytałem. Wydaje się, że obejmuje podstawową teorię, ale nie jestem wystarczająco zaznajomiony z tym tematem, aby ocenić, jak kompleksowo:

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

Optymalne stabilne łączenie

Antonios Symvonis

W tym artykule pokazano, jak stabilnie połączyć dwie sekwencje A i B o rozmiarach odpowiednio odpowiednio m, n, m ≤ n, z przypisaniami O (m + n), porównaniami O (mlog (n / m + 1)) i stosując tylko stałą ilość dodatkowej przestrzeni. Ten wynik pasuje do wszystkich znanych dolnych granic ...

To naprawdę nie jest łatwe ani wydajne, i sugeruję, abyś tego nie robił, chyba że naprawdę musisz (i prawdopodobnie nie musisz, chyba że jest to praca domowa, ponieważ zastosowania łączenia w miejscu są głównie teoretyczne). Nie możesz zamiast tego użyć Quicksort? Quicksort i tak będzie szybszy z kilkoma prostszymi optymalizacjami, a jego dodatkowa pamięć to O (log N) .

W każdym razie, jeśli musisz to zrobić, musisz. Oto, co znalazłem: jeden i dwa . Nie jestem zaznajomiony z rodzajem scalania, ale wydaje się, że podstawową ideą jest użycie rotacji, aby ułatwić scalenie dwóch tablic bez użycia dodatkowej pamięci.

Zauważ, że jest to wolniejsze, nawet niż klasyczny sposób scalania, który nie jest na miejscu.

Krytycznym krokiem jest doprowadzenie do samego scalenia . Te źródła nie są tak trudne, jak to zauważają, ale tracisz coś, próbując.

Patrząc na jeden etap scalania:

[... posortowane według listy ... | x ... lista- A ... | y ... lista- B ...]

Wiemy, że sortowane sekwencja jest mniejsza niż wszystko inne, że x jest mniejsza niż wszystko inne w A , a y jest mniejsza niż wszystko inne w B . W przypadku, gdy x jest mniejsze lub równe y , po prostu przesuń wskaźnik na początek litery A na jednym. W przypadku, gdy y jest mniejsze niż x , musisz przetasować y przez całe A, aby posortować . Ten ostatni krok sprawia, że ​​jest to kosztowne (z wyjątkiem przypadków zdegenerowanych).

Generalnie jest to tańsze (szczególnie gdy tablice zawierają tylko pojedyncze słowa na element, np. Wskaźnik do łańcucha lub struktury), aby zamienić trochę miejsca na czas i mieć oddzielną tablicę tymczasową, między którą sortujesz.

Dla porównania, tutaj jest ładna implementacja stabilnego typu scalania w miejscu . Skomplikowane, ale nie tak źle.

Skończyło się na wdrożeniu zarówno stabilnego sortowania scalającego w miejscu, jak i stabilnego szybkiego sortowania w Javie. Uwaga: złożoność wynosi O (n (log n) ^ 2)

Przykład bezbuforowego scalania w 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);
     }
}

Przykład adaptacyjnego scalania (zoptymalizowanego).

Dodaje kod pomocniczy i modyfikacje, aby przyspieszyć scalanie, gdy dostępny jest bufor pomocniczy dowolnego rozmiaru (nadal działa bez dodatkowej pamięci). Wykorzystuje scalanie do przodu i do tyłu, obracanie pierścienia, scalanie i sortowanie w małej sekwencji oraz iteracyjny scalanie.

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

Ta odpowiedź zawiera przykład kodu , który implementuje algorytm opisany w artykule Practical In-Place Scalenie autorstwa Bing-Chao Huanga i Michaela A. Langstona. Muszę przyznać, że nie rozumiem szczegółów, ale podana złożoność kroku scalania to O (n).

Z praktycznego punktu widzenia istnieją dowody na to, że zwykłe wdrożenia na miejscu nie sprawdzają się lepiej w scenariuszach rzeczywistych. Na przykład standard C ++ definiuje std :: inplace_merge , co oznacza, że ​​nazwa sugeruje operację scalania w miejscu.

Zakładając, że biblioteki C ++ są zazwyczaj bardzo dobrze zoptymalizowane, ciekawe jest, jak to zaimplementować:

1) libstdc ++ (część bazy kodu GCC): std :: inplace_merge

Implementacja deleguje do __inplace_merge , co pozwala uniknąć problemu, próbując przydzielić tymczasowy bufor:

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

W przeciwnym razie wraca do implementacji ( __merge_without_buffer ), która nie wymaga dodatkowej pamięci, ale nie działa już w czasie O (n).

2) libc ++ (część bazy kodu Clanga): std :: inplace_merge

Wygląda podobnie. Deleguje się do funkcji , która również próbuje przydzielić bufor . W zależności od tego, czy ma wystarczającą liczbę elementów, wybierze implementację. Funkcja zastępowania pamięci stałej nazywa się __buffered_inplace_merge .

Być może nawet powrót jest nadal czasem O (n), ale chodzi o to, że nie używają implementacji, jeśli dostępna jest pamięć tymczasowa.

Zauważ, że standard C ++ wyraźnie daje implementacjom swobodę wyboru tego podejścia poprzez obniżenie wymaganej złożoności z O (n) do O (N log N):

Złożoność: Dokładne porównania N-1, jeśli dostępna jest wystarczająca ilość dodatkowej pamięci. Jeśli pamięć jest niewystarczająca, porównania O (N log N).

Oczywiście nie można tego uznać za dowód, że nigdy nie należy wykorzystywać stałej przestrzeni w miejscu w czasie O (n). Z drugiej strony, jeśli byłoby to szybsze, zoptymalizowane biblioteki C ++ prawdopodobnie przełączyłyby się na tego rodzaju implementację.

To jest moja wersja 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--;
    }
  }
}

Istnieje względnie prosta implementacja sortowania scalającego na miejscu przy użyciu oryginalnej techniki Kronrod, ale z prostszą implementacją. Obrazowy przykład ilustrujący tę technikę można znaleźć tutaj: http://www.logiccoder.com/TheSortProblem/BestMergeInfo.htm .

Istnieją również linki do bardziej szczegółowej analizy teoretycznej tego samego autora powiązanej z tym linkiem.

Właśnie próbowałem w miejscu algorytmu scalania sortowania scalającego w JAVA , używając algorytmu sortowania wstawiania, wykonując następujące kroki.
1) Dostępne są dwa uporządkowane tablice.
2) Porównaj pierwsze wartości każdej tablicy; i umieść najmniejszą wartość w pierwszej tablicy.
3) Umieść większą wartość w drugiej tablicy, używając sortowania wstawiania (przesuwaj od lewej do prawej).
4) Następnie ponownie porównaj drugą wartość pierwszej tablicy i pierwszą wartość drugiej tablicy i zrób to samo. Ale kiedy następuje zamiana, istnieje pewna wskazówka dotycząca pominięcia przy porównywaniu dalszych elementów, ale wymagana jest tylko zamiana.

Dokonałem tutaj optymalizacji; aby zachować mniejsze porównania w rodzaju wstawiania.
Jedyną wadą, jaką znalazłem w przypadku tych rozwiązań, jest to, że wymaga większej wymiany elementów tablicy w drugiej tablicy.

na przykład)

Pierwszy___ Tablica: 3, 7, 8, 9

Drugi zestaw: 1, 2, 4, 5

Następnie 7, 8, 9 sprawia, że ​​druga tablica zamienia (przesuwa się w lewo o jeden) wszystkie swoje elementy za każdym razem, aby umieścić się w ostatniej.

Zatem tutaj założenie, że zamiana przedmiotów jest pomijalne w porównaniu z porównywaniem dwóch przedmiotów.

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