Bagaimana cara mengurutkan di tempat menggunakan algoritma pengurutan gabungan?

Saya tahu pertanyaannya tidak terlalu spesifik.

Yang saya inginkan adalah seseorang memberi tahu saya cara mengonversi jenis gabungan normal menjadi jenis gabungan di tempat (atau semacam gabungan dengan overhead ruang ekstra konstan).

Yang bisa saya temukan (di internet) adalah halaman yang mengatakan "terlalu rumit" atau "di luar jangkauan teks ini".

Satu-satunya cara yang diketahui untuk menggabungkan di tempat (tanpa ruang tambahan) terlalu rumit untuk direduksi menjadi program praktis. (diambil dari sini )

Bahkan jika itu terlalu kompleks, apa konsep dasar bagaimana membuat penggabungan di tempat?

Knuth meninggalkan ini sebagai latihan (Vol 3, 5.2.5). Memang ada jenis penggabungan di tempat. Mereka harus diimplementasikan dengan hati-hati.

Pertama, penggabungan naif di tempat seperti yang dijelaskan di sini bukan solusi yang tepat. Ini menurunkan kinerja ke O (N ² ) .

Idenya adalah untuk mengurutkan bagian dari array saat menggunakan sisanya sebagai area kerja untuk penggabungan.

Misalnya seperti fungsi gabungan berikut.

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

Dibutuhkan array xs, dua sub-array yang diurutkan diwakili sebagai rentang [i, m)dan [j, n)masing - masing. Wilayah kerja dimulai dari w. Bandingkan dengan algoritma penggabungan standar yang diberikan di sebagian besar buku teks, yang satu ini bertukar konten antara sub-array yang diurutkan dan area kerja. Akibatnya, area kerja sebelumnya berisi elemen yang diurutkan gabungan, sedangkan elemen sebelumnya yang disimpan di area kerja dipindahkan ke dua sub-array.

Namun, ada dua kendala yang harus dipenuhi:

1. Area kerja harus dalam batas array. Dengan kata lain, itu harus cukup besar untuk menahan elemen dipertukarkan tanpa menyebabkan kesalahan di luar batas.
2. Area kerja dapat tumpang tindih dengan salah satu dari dua array yang diurutkan; Namun, harus memastikan bahwa tidak ada elemen yang tidak ditimpa yang ditimpa.

Dengan algoritma penggabungan ini ditentukan, mudah untuk membayangkan solusi, yang dapat mengurutkan setengah dari array; Pertanyaan selanjutnya adalah, bagaimana menangani sisa bagian yang tidak disortir yang disimpan di area kerja seperti yang ditunjukkan di bawah ini:

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

Satu ide intuitif adalah mengurutkan rekursif setengah dari area kerja, sehingga hanya ada 1/4 elemen yang belum disortir.

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

Titik kunci pada tahap ini adalah bahwa kita harus menggabungkan elemen 1/4 yang disortir B dengan elemen 1/2 yang diurutkan Cepat atau lambat.

Apakah area kerja tersisa, yang hanya menampung 1/4 elemen, cukup besar untuk menggabungkan A dan B? Sayangnya tidak.

Namun, kendala kedua yang disebutkan di atas memberi kita petunjuk, bahwa kita dapat mengeksploitasinya dengan mengatur area kerja untuk tumpang tindih dengan salah satu sub-array jika kita dapat memastikan urutan penggabungan bahwa elemen yang tidak digabungkan tidak akan ditimpa.

Sebenarnya, alih-alih mengurutkan bagian kedua dari area kerja, kita dapat mengurutkan bagian pertama, dan menempatkan area kerja di antara dua array yang diurutkan seperti ini:

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

Pengaturan ini secara efektif mengatur area kerja yang tumpang tindih dengan sub-array A. Ide ini diusulkan di [Jyrki Katajainen, Tomi Pasanen, Jukka Teuhola. `` Praktis di tempat mergesort ''. Nordic Journal of Computing, 1996].

Jadi satu-satunya yang tersisa adalah mengulangi langkah di atas, yang mengurangi area kerja dari 1/2, 1/4, 1/8, ... Ketika area kerja menjadi cukup kecil (misalnya, hanya dua elemen yang tersisa), kita dapat beralih ke jenis penyisipan sepele untuk mengakhiri algoritma ini.

Berikut ini adalah implementasi dalam ANSI C berdasarkan makalah ini.

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

Di mana wmerge didefinisikan sebelumnya.

Kode sumber lengkap dapat ditemukan di sini dan penjelasan terperinci dapat ditemukan di sini

Omong-omong, versi ini bukan jenis penggabungan tercepat karena membutuhkan lebih banyak operasi swap. Menurut pengujian saya, ini lebih cepat daripada versi standar, yang mengalokasikan ruang ekstra di setiap rekursi. Tetapi lebih lambat dari versi yang dioptimalkan, yang menggandakan array asli di muka dan menggunakannya untuk penggabungan lebih lanjut.

Termasuk "hasil besarnya", makalah ini menjelaskan beberapa varian jenis penggabungan in-place (PDF):

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

Pengurutan di tempat dengan sedikit gerakan

Jyrki Katajainen, Tomi A. Pasanen

Terlihat bahwa susunan elemen n dapat diurutkan menggunakan O (1) ruang ekstra, elemen O (n log n / log n) bergerak, dan perbandingan n log ₂ n + O (n log log n). Ini adalah algoritma pengurutan di tempat pertama yang membutuhkan o (n log n) bergerak dalam kasus terburuk sekaligus menjamin perbandingan O (n log n), tetapi karena faktor-faktor konstan yang terlibat, algoritma ini lebih banyak diminati secara teoritis.

Saya pikir ini juga relevan. Saya memiliki cetakannya yang tergeletak, diserahkan kepada saya oleh seorang kolega, tetapi saya belum membacanya. Tampaknya mencakup teori dasar, tapi saya tidak cukup akrab dengan topik untuk menilai seberapa komprehensif:

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

Penggabungan Stabil Optimal

Antonios Symvonis

Makalah ini menunjukkan bagaimana menggabungkan secara stabil dua urutan A dan B ukuran m dan n, m ≤ n, masing-masing, dengan penugasan O (m + n), perbandingan O (mlog (n / m + 1)) dan hanya menggunakan konstanta jumlah ruang tambahan. Hasil ini cocok dengan semua batas bawah yang diketahui ...

Ini benar-benar tidak mudah atau efisien, dan saya sarankan Anda tidak melakukannya kecuali Anda benar-benar harus (dan Anda mungkin tidak harus kecuali jika ini adalah pekerjaan rumah karena aplikasi penggabungan inplace sebagian besar bersifat teoritis). Tidak bisakah Anda menggunakan quicksort saja? Quicksort akan lebih cepat pula dengan beberapa optimasi sederhana dan memori ekstra adalah O (log N) .

Bagaimanapun, jika Anda harus melakukannya maka Anda harus melakukannya. Inilah yang saya temukan: satu dan dua . Saya tidak terbiasa dengan inge merge sort, tetapi sepertinya ide dasarnya adalah menggunakan rotasi untuk memfasilitasi penggabungan dua array tanpa menggunakan memori tambahan.

Perhatikan bahwa ini lebih lambat bahkan dari jenis penggabungan klasik yang tidak ada.

Langkah penting adalah mendapatkan penggabungan itu sendiri di tempat. Ini tidak sesulit sumber-sumber itu, tetapi Anda kehilangan sesuatu ketika mencoba.

Melihat satu langkah penggabungan:

[... daftar- disortir ... | x ... daftar- A ... | y ... daftar- B ...]

Kita tahu bahwa diurutkan urutan kurang dari segala sesuatu yang lain, yang x kurang dari segala sesuatu yang lain di A , dan yang y kurang dari segala sesuatu yang lain di B . Dalam kasus di mana x kurang dari atau sama dengan y , Anda hanya memindahkan pointer Anda ke awal A satu. Dalam kasus di mana y kurang dari x , Anda harus mengocok y melewati seluruh A untuk diurutkan . Langkah terakhir itulah yang membuat ini mahal (kecuali dalam kasus degenerasi).

Ini umumnya lebih murah (terutama ketika array hanya benar-benar berisi kata tunggal per elemen, misalnya, pointer ke string atau struktur) untuk menukar ruang untuk waktu dan memiliki array sementara terpisah yang Anda sortir bolak-balik.

Hanya untuk referensi, berikut adalah implementasi yang bagus dari semacam gabungan tempat yang stabil . Rumit, tapi tidak terlalu buruk.

Saya akhirnya mengimplementasikan kedua jenis penggabungan in-place yang stabil dan quicksort in -place yang stabil di Jawa. Harap perhatikan kompleksitasnya adalah O (n (log n) ^ 2)

Contoh mergesort tanpa buffer di 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);
     }
}

Contoh mergesort adaptif (dioptimalkan).

Menambahkan kode dukungan dan modifikasi untuk mempercepat penggabungan ketika buffer tambahan dalam berbagai ukuran tersedia (masih berfungsi tanpa memori tambahan). Menggunakan penggabungan maju dan mundur, rotasi cincin, penggabungan dan penyortiran urutan kecil, dan penggabungan berulang.

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

Jawaban ini memiliki contoh kode , yang mengimplementasikan algoritma yang dijelaskan dalam makalah Praktis Penggabungan In-Place oleh Bing-Chao Huang dan Michael A. Langston. Saya harus mengakui bahwa saya tidak mengerti detailnya, tetapi kompleksitas langkah penggabungan yang diberikan adalah O (n).

Dari perspektif praktis, ada bukti bahwa implementasi murni di tempat tidak berkinerja lebih baik dalam skenario dunia nyata. Sebagai contoh, standar C ++ mendefinisikan std :: inplace_merge , yang seperti namanya mengimplikasikan operasi penggabungan in-place.

Dengan asumsi bahwa pustaka C ++ biasanya dioptimalkan dengan sangat baik, menarik untuk melihat bagaimana itu diimplementasikan:

1) libstdc ++ (bagian dari basis kode GCC): std :: inplace_merge

Delegasi implementasi ke __inplace_merge , yang menghindari masalah dengan mencoba mengalokasikan buffer sementara:

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

Kalau tidak, ia kembali ke implementasi ( __merge_without_buffer ), yang tidak memerlukan memori tambahan, tetapi tidak lagi berjalan dalam waktu O (n).

2) libc ++ (bagian dari basis kode Dentang ): std :: inplace_merge

Terlihat mirip. Ini mendelegasikan ke fungsi , yang juga mencoba untuk mengalokasikan buffer . Bergantung pada apakah elemennya cukup, ia akan memilih implementasinya. Fungsi fallback memori konstan disebut __buffered_inplace_merge .

Mungkin bahkan mundur masih O (n) waktu, tetapi intinya adalah bahwa mereka tidak menggunakan implementasi jika memori sementara tersedia.

Perhatikan bahwa standar C ++ secara eksplisit memberikan implementasi kebebasan untuk memilih pendekatan ini dengan menurunkan kompleksitas yang diperlukan dari O (n) ke O (N log N):

Kompleksitas: Perbandingan N-1 yang tepat jika tersedia memori tambahan yang cukup. Jika memori tidak mencukupi, perbandingan O (N log N).

Tentu saja, ini tidak dapat diambil sebagai bukti bahwa ruang konstan di tempat bergabung dalam waktu O (n) tidak boleh digunakan. Di sisi lain, jika akan lebih cepat, pustaka C ++ yang dioptimalkan mungkin akan beralih ke jenis implementasi tersebut.

Ini adalah versi C saya:

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

Ada implementasi yang relatif sederhana dari jenis penggabungan in-place menggunakan teknik asli Kronrod tetapi dengan implementasi yang lebih sederhana. Contoh gambar yang menggambarkan teknik ini dapat ditemukan di sini: http://www.logiccoder.com/TheSortProblem/BestMergeInfo.htm .

Ada juga tautan ke analisis teoretis yang lebih rinci oleh penulis yang sama yang terkait dengan tautan ini.

Saya baru saja mencoba di tempat menggabungkan algoritma untuk menggabungkan semacam di JAWA dengan menggunakan algoritma semacam penyisipan, menggunakan langkah-langkah berikut.
1) Tersedia dua array yang diurutkan.
2) Bandingkan nilai pertama dari setiap array; dan tempatkan nilai terkecil ke dalam array pertama.
3) Tempatkan nilai yang lebih besar ke dalam array kedua dengan menggunakan jenis penyisipan (melintasi dari kiri ke kanan).
4) Kemudian bandingkan lagi nilai kedua array pertama dan nilai pertama array kedua, dan lakukan hal yang sama. Tetapi ketika bertukar terjadi ada beberapa petunjuk tentang melompat membandingkan item lebih lanjut, tetapi hanya bertukar diperlukan.

Saya telah membuat beberapa optimasi di sini; untuk menjaga perbandingan yang lebih rendah dalam jenis penyisipan.
Satu-satunya kelemahan yang saya temukan dengan solusi ini adalah perlu swapping elemen array yang lebih besar di array kedua.

misalnya)

First___Array: 3, 7, 8, 9

Array Kedua: 1, 2, 4, 5

Kemudian 7, 8, 9 membuat array kedua untuk bertukar (bergerak ke kiri oleh satu) semua elemennya dengan satu setiap kali menempatkan dirinya di yang terakhir.

Jadi asumsi di sini adalah menukar item dapat diabaikan dibandingkan dengan membandingkan dua item.

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