Wie sortiere ich direkt mit dem Sortieralgorithmus?

Ich weiß, dass die Frage nicht zu spezifisch ist.

Ich möchte nur, dass mir jemand sagt, wie eine normale Zusammenführungssortierung in eine direkte Zusammenführungssortierung (oder eine Zusammenführungssortierung mit konstantem zusätzlichen Speicherplatzaufwand) konvertiert wird.

Alles, was ich (im Internet) finden kann, sind Seiten, auf denen steht "es ist zu komplex" oder "außerhalb des Geltungsbereichs dieses Textes".

Die einzigen bekannten Möglichkeiten zum Zusammenführen an Ort und Stelle (ohne zusätzlichen Speicherplatz) sind zu komplex, um auf ein praktisches Programm reduziert zu werden. ( von hier genommen )

Auch wenn es zu komplex ist, wie sieht das Grundkonzept aus, wie die Zusammenführungssortierung eingerichtet wird?

Knuth ließ dies als Übung (Band 3, 5.2.5). Es gibt In-Place-Zusammenführungssorten. Sie müssen sorgfältig umgesetzt werden.

Erstens ist eine naive In-Place-Zusammenführung wie hier beschrieben nicht die richtige Lösung. Die Leistung wird auf O (N ² ) herabgestuft .

Die Idee ist, einen Teil des Arrays zu sortieren, während der Rest als Arbeitsbereich zum Zusammenführen verwendet wird.

Zum Beispiel wie die folgende Zusammenführungsfunktion.

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

Es nimmt die Anordnung xs, die zwei sortierten Subarrays werden als Bereiche dargestellt [i, m)und [j, n)jeweils. Der Arbeitsbereich beginnt ab w. Vergleichen Sie mit dem Standard-Zusammenführungsalgorithmus, der in den meisten Lehrbüchern angegeben ist. Dieser tauscht den Inhalt zwischen dem sortierten Unterarray und dem Arbeitsbereich aus. Infolgedessen enthält der vorherige Arbeitsbereich die zusammengeführten sortierten Elemente, während die im Arbeitsbereich gespeicherten vorherigen Elemente in die beiden Unterarrays verschoben werden.

Es gibt jedoch zwei Einschränkungen, die erfüllt sein müssen:

1. Der Arbeitsbereich sollte innerhalb der Grenzen des Arrays liegen. Mit anderen Worten, es sollte groß genug sein, um ausgetauschte Elemente aufzunehmen, ohne einen Fehler außerhalb der Grenze zu verursachen.
2. Der Arbeitsbereich kann mit einem der beiden sortierten Arrays überlappt werden. Es muss jedoch sichergestellt werden, dass keines der nicht zusammengeführten Elemente überschrieben wird.

Wenn dieser Zusammenführungsalgorithmus definiert ist, kann man sich leicht eine Lösung vorstellen, mit der die Hälfte des Arrays sortiert werden kann. Die nächste Frage ist, wie mit dem Rest des unsortierten Teils umgegangen werden soll, der im Arbeitsbereich gespeichert ist, wie unten gezeigt:

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

Eine intuitive Idee besteht darin, eine weitere Hälfte des Arbeitsbereichs rekursiv zu sortieren, sodass nur 1/4 Elemente noch nicht sortiert wurden.

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

Der entscheidende Punkt in dieser Phase ist, dass wir die sortierten 1/4 Elemente B früher oder später mit den sortierten 1/2 Elementen A zusammenführen müssen.

Ist der Arbeitsbereich, der nur 1/4 Elemente enthält, groß genug, um A und B zusammenzuführen? Leider ist es nicht.

Die oben erwähnte zweite Einschränkung gibt uns jedoch einen Hinweis, dass wir sie ausnutzen können, indem wir den Arbeitsbereich so anordnen, dass er sich mit einem der beiden Unterarrays überlappt, wenn wir sicherstellen können, dass die Zusammenführungssequenz nicht überschrieben wird.

Anstatt die zweite Hälfte des Arbeitsbereichs zu sortieren, können wir auch die erste Hälfte sortieren und den Arbeitsbereich wie folgt zwischen die beiden sortierten Arrays einfügen:

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

Dieser Aufbau ordnet effektiv die Überlappung des Arbeitsbereichs mit dem Subarray A an. Diese Idee wird in [Jyrki Katajainen, Tomi Pasanen, Jukka Teuhola. "Praktisches In-Place-Mergesort". Nordic Journal of Computing, 1996].

Das einzige, was noch übrig ist, ist, den obigen Schritt zu wiederholen, wodurch der Arbeitsbereich von 1/2, 1/4, 1/8, ... reduziert wird. Wenn der Arbeitsbereich klein genug wird (zum Beispiel nur noch zwei Elemente übrig), können wir Wechseln Sie zu einer einfachen Einfügungssortierung, um diesen Algorithmus zu beenden.

Hier ist die Implementierung in ANSI C basierend auf diesem Dokument.

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

Wo wmerge zuvor definiert wurde.

Den vollständigen Quellcode finden Sie hier und die ausführliche Erklärung finden Sie hier

Diese Version ist übrigens nicht die schnellste Zusammenführungssortierung, da mehr Auslagerungsvorgänge erforderlich sind. Meinem Test zufolge ist es schneller als die Standardversion, die bei jeder Rekursion zusätzliche Leerzeichen zuweist. Es ist jedoch langsamer als die optimierte Version, bei der das ursprüngliche Array im Voraus verdoppelt und für die weitere Zusammenführung verwendet wird.

Inklusive des "großen Ergebnisses" beschreibt dieses Papier einige Varianten der In-Place-Merge-Sortierung (PDF):

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

In-Place-Sortierung mit weniger Zügen

Jyrki Katajainen, Tomi A. Pasanen

Es wird gezeigt, dass ein Array von n Elementen unter Verwendung von O (1) zusätzlichem Speicherplatz, O (n log n / log log n) Elementbewegungen und n log ₂ n + O (n log log n) Vergleichen sortiert werden kann . Dies ist der erste In-Place-Sortieralgorithmus, der im schlimmsten Fall o (n log n) Bewegungen erfordert und gleichzeitig O (n log n) Vergleiche garantiert. Aufgrund der konstanten Faktoren ist der Algorithmus jedoch überwiegend von theoretischem Interesse.

Ich denke, das ist auch relevant. Ich habe einen Ausdruck davon herumliegen, der mir von einem Kollegen weitergegeben wurde, aber ich habe ihn nicht gelesen. Es scheint die grundlegende Theorie abzudecken, aber ich bin mit dem Thema nicht vertraut genug, um zu beurteilen, wie umfassend:

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

Optimale stabile Zusammenführung

Antonios Symvonis

Diese Arbeit zeigt, wie zwei Sequenzen A und B der Größen m und n, m ≤ n stabil mit O (m + n) -Zuweisungen, O (mlog (n / m + 1)) -Vergleichen und nur unter Verwendung einer Konstanten zusammengeführt werden können Menge zusätzlichen Platzes. Dieses Ergebnis stimmt mit allen bekannten Untergrenzen überein ...

Es ist wirklich nicht einfach oder effizient, und ich schlage vor, Sie tun es nur, wenn Sie es wirklich müssen (und Sie müssen es wahrscheinlich nicht tun, es sei denn, dies sind Hausaufgaben, da die Anwendungen des Inplace-Zusammenführens größtenteils theoretisch sind). Können Sie nicht stattdessen Quicksort verwenden? Quicksort wird mit ein paar einfacheren Optimierungen sowieso schneller sein und sein zusätzlicher Speicher ist O (log N) .

Wie auch immer, wenn Sie es tun müssen, dann müssen Sie. Folgendes habe ich gefunden: eins und zwei . Ich bin nicht mit der Inplace-Merge-Sortierung vertraut, aber es scheint, dass die Grundidee darin besteht, Rotationen zu verwenden, um das Zusammenführen von zwei Arrays ohne zusätzlichen Speicher zu erleichtern.

Beachten Sie, dass dies sogar langsamer ist als die klassische Zusammenführungssortierung, die nicht vorhanden ist.

Der entscheidende Schritt besteht darin, die Zusammenführung selbst in Kraft zu setzen. Es ist nicht so schwierig, wie diese Quellen ausmachen, aber Sie verlieren etwas, wenn Sie es versuchen.

Betrachten Sie einen Schritt der Zusammenführung:

[... Listen- sortiert ... | x ... Liste- A ... | y ... Liste- B ...]

Wir wissen , dass die sortierten Sequenz als alles weniger ist anders, dass x weniger als alles andere in A , und daß y kleiner ist als alles andere in B . In dem Fall, in dem x kleiner oder gleich y ist , bewegen Sie einfach Ihren Zeiger auf den Anfang von A auf eins. In dem Fall, in dem y kleiner als x ist , müssen Sie y über das gesamte A mischen, um es zu sortieren . Dieser letzte Schritt macht dies teuer (außer in entarteten Fällen).

Es ist im Allgemeinen billiger (insbesondere wenn die Arrays nur einzelne Wörter pro Element enthalten, z. B. einen Zeiger auf eine Zeichenfolge oder Struktur), etwas Zeit für Zeit auszutauschen und ein separates temporäres Array zu haben, zwischen dem Sie hin und her sortieren.

Nur als Referenz, hier ist eine schöne Implementierung einer stabilen In-Place-Merge-Sortierung . Kompliziert, aber nicht schlecht.

Am Ende habe ich sowohl eine stabile In-Place-Merge-Sortierung als auch eine stabile In-Place-Quicksortierung in Java implementiert . Bitte beachten Sie, dass die Komplexität O (n (log n) ^ 2) ist.

Ein Beispiel für eine pufferlose Zusammenführung in C.

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

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

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

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

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

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

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

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

Ein Beispiel für adaptives Mergesort (optimiert).

Fügt Support-Code und Änderungen hinzu, um die Zusammenführung zu beschleunigen, wenn ein Hilfspuffer beliebiger Größe verfügbar ist (funktioniert immer noch ohne zusätzlichen Speicher). Verwendet Vorwärts- und Rückwärtszusammenführung, Ringrotation, Zusammenführen und Sortieren kleiner Sequenzen und iteratives Zusammenführen.

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

Diese Antwort enthält ein Codebeispiel , das den im Artikel Praktisches In-Place-Zusammenführen beschriebenen Algorithmus implementiert von Bing-Chao Huang und Michael A. Langston beschrieben ist. Ich muss zugeben, dass ich die Details nicht verstehe, aber die gegebene Komplexität des Zusammenführungsschritts ist O (n).

Aus praktischer Sicht gibt es Hinweise darauf, dass reine In-Place-Implementierungen in realen Szenarien keine bessere Leistung erbringen. Beispielsweise definiert der C ++ - Standard std :: inplace_merge , was bedeutet , dass der Name eine direkte Zusammenführungsoperation impliziert.

Unter der Annahme, dass C ++ - Bibliotheken normalerweise sehr gut optimiert sind, ist es interessant zu sehen, wie sie implementiert werden:

1) libstdc ++ (Teil der GCC-Codebasis): std :: inplace_merge

Die Implementierung delegiert an __inplace_merge , wodurch das Problem umgangen wird , indem versucht wird, einen temporären Puffer zuzuweisen:

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

Andernfalls wird auf eine Implementierung ( __merge_without_buffer ) zurückgegriffen, die keinen zusätzlichen Speicher benötigt, aber nicht mehr in O (n) -Zeit ausgeführt wird.

2) libc ++ (Teil der Clang-Codebasis): std :: inplace_merge

Sieht ähnlich aus. Es delegiert an eine Funktion , die auch versucht, einen Puffer zuzuweisen . Je nachdem, ob genügend Elemente vorhanden sind, wird die Implementierung ausgewählt. Die Fallback-Funktion für konstanten Speicher heißt __buffered_inplace_merge .

Vielleicht ist sogar der Fallback noch O (n) -Zeit, aber der Punkt ist, dass sie die Implementierung nicht verwenden, wenn temporärer Speicher verfügbar ist.

Beachten Sie, dass der C ++ - Standard Implementierungen explizit die Freiheit gibt, diesen Ansatz zu wählen, indem die erforderliche Komplexität von O (n) auf O (N log N) verringert wird:

Komplexität: Genau N-1-Vergleiche, wenn genügend zusätzlicher Speicher verfügbar ist. Wenn der Speicher nicht ausreicht, werden O (N log N) Vergleiche durchgeführt.

Dies kann natürlich nicht als Beweis dafür angesehen werden, dass ein konstanter Raum an Ort und Stelle, der in O (n) Zeit verschmilzt, niemals verwendet werden sollte. Wenn es jedoch schneller wäre, würden die optimierten C ++ - Bibliotheken wahrscheinlich auf diese Art der Implementierung umsteigen.

Dies ist meine C-Version:

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

Es gibt eine relativ einfache Implementierung der In-Place-Merge-Sortierung unter Verwendung der ursprünglichen Technik von Kronrod, jedoch mit einer einfacheren Implementierung. Ein bildliches Beispiel, das diese Technik veranschaulicht, finden Sie hier: http://www.logiccoder.com/TheSortProblem/BestMergeInfo.htm .

Es gibt auch Links zu detaillierteren theoretischen Analysen desselben Autors, die mit diesem Link verbunden sind.

Ich habe gerade versucht, einen Zusammenführungsalgorithmus für die Zusammenführungssortierung in JAVA mithilfe des Einfügesortieralgorithmus zu verwenden. Dabei wurden die folgenden Schritte ausgeführt.
1) Es stehen zwei sortierte Arrays zur Verfügung.
2) Vergleichen Sie die ersten Werte jedes Arrays; und platzieren Sie den kleinsten Wert in das erste Array.
3) Platzieren Sie den größeren Wert mithilfe der Einfügesortierung (von links nach rechts durchlaufen) in das zweite Array.
4) Vergleichen Sie dann erneut den zweiten Wert des ersten Arrays und den ersten Wert des zweiten Arrays und machen Sie dasselbe. Wenn jedoch ein Austausch stattfindet, gibt es einen Hinweis darauf, dass der Vergleich der weiteren Elemente übersprungen wird, aber nur ein Austausch erforderlich ist.

Ich habe hier einige Optimierungen vorgenommen. um kleinere Vergleiche in der Einfügesortierung zu halten.
Der einzige Nachteil, den ich bei diesen Lösungen festgestellt habe, ist, dass die Array-Elemente im zweiten Array stärker ausgetauscht werden müssen.

z.B)

First___Array: 3, 7, 8, 9

Zweites Array: 1, 2, 4, 5

Dann bewirkt 7, 8, 9, dass das zweite Array alle seine Elemente jedes Mal um eins vertauscht (nach links bewegt), um sich im letzten zu platzieren.

Die Annahme, dass hier Gegenstände ausgetauscht werden, ist im Vergleich zum Vergleich zweier Gegenstände vernachlässigbar.

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