Ik weet dat de vraag niet al te specifiek is.
Het enige wat ik wil, is dat iemand me vertelt hoe ik een normale merge-sortering kan omzetten in een in-place merge-sortering (of een merge-sortering met constante extra ruimte overhead).
Alles wat ik kan vinden (op het net) zijn pagina’s die zeggen “het is te ingewikkeld” of “buiten het bestek van deze tekst”.
De enige bekende manieren om ter plaatse samen te voegen (zonder extra ruimte) zijn te complex om te worden teruggebracht tot een praktisch programma. (van hier)
Zelfs als het te complex is, wat is het basisconcept om de samenvoeging ter plaatse te sorteren?
Antwoord 1, autoriteit 100%
Knuth heeft dit als oefening achtergelaten (Vol 3, 5.2.5). Er bestaan in-place samenvoegsoorten. Ze moeten zorgvuldig worden geïmplementeerd.
Eerst, naïeve in-place merge zoals beschreven hieris niet de juiste oplossing. Het verlaagt de prestaties naar O(N2).
Het idee is om een deel van de array te sorteren en de rest te gebruiken als werkgebied voor het samenvoegen.
Bijvoorbeeld zoals de volgende samenvoegfunctie.
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++);
}
Hiervoor is de array xsnodig, de twee gesorteerde subarrays worden weergegeven als bereiken [i, m)en [j, n)respectievelijk. Het werkgebied begint vanaf w. Vergelijk met het standaard samenvoegalgoritme dat in de meeste leerboeken wordt gegeven, deze wisselt de inhoud uit tussen de gesorteerde subarray en het werkgebied. Het resultaat is dat het vorige werkgebied de samengevoegde gesorteerde elementen bevat, terwijl de vorige elementen die in het werkgebied zijn opgeslagen naar de twee subarrays worden verplaatst.
Er zijn echter twee beperkingen waaraan moet worden voldaan:
- Het werkgebied moet binnen de grenzen van de array liggen. Met andere woorden, het moet groot genoeg zijn om uitgewisselde elementen te bevatten zonder enige out-of-bound-fout te veroorzaken.
- Het werkgebied kan worden overlapt met een van de twee gesorteerde arrays; het moet er echter voor zorgen dat geen van de niet-samengevoegde elementen wordt overschreven.
Met dit samenvoegalgoritme gedefinieerd, is het gemakkelijk om een oplossing voor te stellen die de helft van de array kan sorteren; De volgende vraag is, hoe om te gaan met de rest van het ongesorteerde deel dat is opgeslagen in het werkgebied, zoals hieronder weergegeven:
... unsorted 1/2 array ... | ... sorted 1/2 array ...
Een intuïtief idee is om een andere helft van het werkgebied recursief te sorteren, dus er zijn slechts 1/4 elementen die nog niet zijn gesorteerd.
... unsorted 1/4 array ... | sorted 1/4 array B | sorted 1/2 array A ...
Het belangrijkste punt in dit stadium is dat we de gesorteerde 1/4 elementen B . moeten samenvoegen
met de gesorteerde 1/2 elementen A vroeg of laat.
Is het werkgebied links, dat slechts 1/4 elementen bevat, groot genoeg om samen te voegen?
A en B? Helaas niet.
De tweede beperking die hierboven is genoemd, geeft ons echter een hint dat we deze kunnen exploiteren door het werkgebied zo te rangschikken dat het overlapt met een van beide sub-arrays, als we ervoor kunnen zorgen dat de samenvoegreeks de niet-samengevoegde elementen niet overschrijft.
In plaats van de tweede helft van het werkgebied te sorteren, kunnen we de eerste helft sorteren en het werkgebied als volgt tussen de twee gesorteerde arrays plaatsen:
... sorted 1/4 array B | unsorted work area | ... sorted 1/2 array A ...
Deze opstelling regelt effectief de overlap van het werkgebied met de subarray A. Dit idee
wordt voorgesteld in [Jyrki Katajainen, Tomi Pasanen, Jukka Teuhola. “Praktische in-place mergesort”. Nordic Journal of Computing, 1996].
Dus het enige dat overblijft is om de bovenstaande stap te herhalen, waardoor het werkgebied wordt verkleind van 1/2, 1/4, 1/8, … Wanneer het werkgebied klein genoeg wordt (er zijn bijvoorbeeld nog maar twee elementen over) , kunnen we overschakelen naar een triviale invoegsortering om dit algoritme te beëindigen.
Hier is de implementatie in ANSI C op basis van dit document.
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);
}
}
Waar wmerge eerder is gedefinieerd.
De volledige broncode is hier te vinden en de gedetailleerde uitleg vindt u hier
Trouwens, deze versie is niet de snelste samenvoegsortering omdat er meer wisselbewerkingen nodig zijn. Volgens mijn test is het sneller dan de standaardversie, die extra spaties toewijst in elke recursie. Maar het is langzamer dan de geoptimaliseerde versie, die de originele array vooraf verdubbelt en gebruikt voor verdere samenvoeging.
Antwoord 2, autoriteit 39%
Inclusief het “grote resultaat”, beschrijft dit artikel een aantal varianten van in-place merge sort (PDF):
http:// citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.5514&rep=rep1&type=pdf
In-place sorteren met minder zetten
Jyrki Katajainen, Tomi A. Pasanen
Er wordt aangetoond dat een array van n
elementen kunnen worden gesorteerd met O(1)
extra ruimte, O(n log n / log log n)
element beweegt, en n log2n + O(n log
log n) vergelijkingen. Dit is de eerste
in-place sorteeralgoritme vereist:
o(n log n) beweegt in het ergste geval
terwijl het garanderen van O (n log n)
vergelijkingen, maar vanwege de constante
factoren die een rol spelen bij het algoritme is
voornamelijk van theoretisch belang.
Ik denk dat dit ook relevant is. Ik heb er een afdruk van liggen, door een collega aan mij doorgegeven, maar ik heb het niet gelezen. Het lijkt de basistheorie te dekken, maar ik ben niet bekend genoeg met het onderwerp om te beoordelen hoe uitgebreid:
http://comjnl.oxfordjournals.org/cgi/content/ samenvatting/38/8/681
Optimale stabiele samenvoeging
Antonios Symvonis
Dit artikel laat zien hoe je stabiel kunt samenvoegen
twee reeksen A en B van de maten m en
n, m ≤ n, respectievelijk met O(m+n)
opdrachten, O(mlog(n/m+1))
vergelijkingen en met alleen een constante
hoeveelheid extra ruimte. Deze
resultaat komt overeen met alle bekende ondergrenzen…
Antwoord 3, autoriteit 8%
Het is echt niet gemakkelijk of efficiënt, en ik stel voor dat je het niet doet tenzij het echt moet (en dat hoeft waarschijnlijk ook niet, tenzij dit huiswerk is, aangezien de toepassingen van inplace mergen meestal theoretisch zijn). Kun je in plaats daarvan geen quicksort gebruiken? Quicksort zal hoe dan ook sneller zijn met een paar eenvoudigere optimalisaties en het extra geheugen is O(log N).
Hoe dan ook, als je het moet doen, dan moet je het doen. Dit is wat ik heb gevonden: éénen twee. Ik ben niet bekend met de inplace merge sort, maar het lijkt erop dat het basisidee is om rotaties te gebruiken om het samenvoegen van twee arrays te vergemakkelijken zonder extra geheugen te gebruiken.
Merk op dat dit zelfs langzamer is dan de klassieke samenvoegsortering die niet op zijn plaats is.
Antwoord 4, autoriteit 7%
De cruciale stap is om de samenvoegingzelf op zijn plaats te krijgen. Het is niet zo moeilijk als die bronnen beweren, maar je verliest iets als je het probeert.
Kijkend naar één stap van het samenvoegen:
[…list-gesorteerd…|x…list-A…|y …list-B…]
We weten dat de gesorteerdereeks kleiner is dan al het andere, dat xkleiner is dan al het andere in A, en dat yis kleiner dan al het andere in B. In het geval dat xkleiner is dan of gelijk is aan y, verplaatst u uw aanwijzer naar het begin van Aop één. In het geval dat ykleiner is dan x, moet je yvoorbij de hele Ashufflen naar gesorteerd. Die laatste stap maakt dit duur (behalve in gedegenereerde gevallen).
Het is over het algemeen goedkoper (vooral wanneer de arrays eigenlijk maar enkele woorden per element bevatten, bijvoorbeeld een aanwijzer naar een string of structuur) om wat ruimte in te ruilen voor tijd en een aparte tijdelijke array te hebben waartussen je heen en weer sorteert.
Antwoord 5, autoriteit 4%
Dit antwoordheeft een codevoorbeeld, dat het algoritme implementeert dat wordt beschreven in de paper Praktische In-Place Mergingdoor Bing-Chao Huang en Michael A. Langston. Ik moet toegeven dat ik de details niet begrijp, maar de gegeven complexiteit van de samenvoegstap is O(n).
Vanuit een praktisch perspectief is er bewijs dat pure in-place implementaties niet beter presteren in real-world scenario’s. De C++-standaard definieert bijvoorbeeld std::inplace_merge, zoals de naam impliceert een interne samenvoegoperatie.
Ervan uitgaande dat C++-bibliotheken doorgaans zeer goed zijn geoptimaliseerd, is het interessant om te zien hoe het wordt geïmplementeerd:
1) libstdc++ (onderdeel van de GCC-codebasis): std::inplace_merge
De implementatie is gedelegeerd aan __inplace_merge, die het probleem ontwijkt door te proberen een tijdelijke buffer toe te wijzen:
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);
Anders valt het terug op een implementatie (__merge_without_buffer), die geen extra geheugen vereist, maar niet langer in O(n)-tijd draait.
2) libc++ (onderdeel van de Clang-codebasis): std::inplace_merge
Lijkt op elkaar. Het delegeert naar een functie, die ook probeert een buffer toewijzen. Afhankelijk van of het genoeg elementen heeft, zal het de implementatie kiezen. De terugvalfunctie voor constant geheugen heet __buffered_inplace_merge.
Misschien is zelfs de terugval nog steeds O(n)-tijd, maar het punt is dat ze de implementatie niet gebruiken als er tijdelijk geheugen beschikbaar is.
Merk op dat de C++-standaard implementaties expliciet de vrijheid geeft om deze benadering te kiezen door de vereiste complexiteit te verlagen van O(n) naar O(N log N):
Complexiteit:
Precies N-1 vergelijkingen als er voldoende extra geheugen beschikbaar is. Als het geheugen onvoldoende is, O(N log N) vergelijkingen.
Natuurlijk kan dit niet worden opgevat als een bewijs dat constante ruimte ter plaatse samenvloeit in O(n)-tijd nooit mag worden gebruikt. Aan de andere kant, als het sneller zou zijn, zouden de geoptimaliseerde C++-bibliotheken waarschijnlijk overschakelen naar dat type implementatie.
Antwoord 6, autoriteit 3%
Een voorbeeld van bufferloze mergesort 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);
}
}
Een voorbeeld van adaptieve mergesort (geoptimaliseerd).
Voegt ondersteuningscode en aanpassingen toe om het samenvoegen te versnellen wanneer een hulpbuffer van elke grootte beschikbaar is (werkt nog steeds zonder extra geheugen). Gebruikt voorwaarts en achterwaarts samenvoegen, ringrotatie, samenvoegen en sorteren van kleine reeksen en iteratief samenvoegen.
#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);
}
Antwoord 7, autoriteit 2%
Dit is mijn C-versie:
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--;
}
}
}
Antwoord 8
Ik weet dat ik te laat ben voor de game, maar hier is een oplossing die ik gisteren schreef. Ik heb dit ook elders gepost, maar dit lijkt de meest populaire merge-in-place thread op SO te zijn. Ik heb dit algoritme ook nergens anders gezien, dus hopelijk helpt dit sommige mensen.
Dit algoritme is in zijn meest eenvoudige vorm, zodat het kan worden begrepen. Het kan aanzienlijk worden aangepast voor extra snelheid. De gemiddelde complexiteit van de tijd is: O(n.log₂n) voor de stabiele in-place array merge, en O(n.(log₂n)²) voor de algehele sortering.
// Stable Merge In Place Sort
//
//
// The following code is written to illustrate the base algorithm. A good
// number of optimizations can be applied to boost its overall speed
// For all its simplicity, it does still perform somewhat decently.
// Average case time complexity appears to be: O(n.(log₂n)²)
#include <stddef.h>
#include <stdio.h>
#define swap(x, y) (t=(x), (x)=(y), (y)=t)
// Both sorted sub-arrays must be adjacent in 'a'
// Assumes that both 'an' and 'bn' are always non-zero
// 'an' is the length of the first sorted section in 'a', referred to as A
// 'bn' is the length of the second sorted section in 'a', referred to as B
static void
merge_inplace(int A[], size_t an, size_t bn)
{
int t, *B = &A[an];
size_t pa, pb; // Swap partition pointers within A and B
// Find the portion to swap. We're looking for how much from the
// start of B can swap with the end of A, such that every element
// in A is less than or equal to any element in B. This is quite
// simple when both sub-arrays come at us pre-sorted
for(pa = an, pb = 0; pa>0 && pb<bn && B[pb] < A[pa-1]; pa--, pb++);
// Now swap last part of A with first part of B according to the
// indicies we found
for (size_t index=pa; index < an; index++)
swap(A[index], B[index-pa]);
// Now merge the two sub-array pairings. We need to check that either array
// didn't wholly swap out the other and cause the remaining portion to be zero
if (pa>0 && (an-pa)>0)
merge_inplace(A, pa, an-pa);
if (pb>0 && (bn-pb)>0)
merge_inplace(B, pb, bn-pb);
} // merge_inplace
// Implements a recursive merge-sort algorithm with an optional
// insertion sort for when the splits get too small. 'n' must
// ALWAYS be 2 or more. It enforces this when calling itself
static void
merge_sort(int a[], size_t n)
{
size_t m = n/2;
// Sort first and second halves only if the target 'n' will be > 1
if (m > 1)
merge_sort(a, m);
if ((n-m)>1)
merge_sort(a+m, n-m);
// Now merge the two sorted sub-arrays together. We know that since
// n > 1, then both m and n-m MUST be non-zero, and so we will never
// violate the condition of not passing in zero length sub-arrays
merge_inplace(a, m, n-m);
} // merge_sort
// Print an array */
static void
print_array(int a[], size_t size)
{
if (size > 0) {
printf("%d", a[0]);
for (size_t i = 1; i < size; i++)
printf(" %d", a[i]);
}
printf("\n");
} // print_array
// Test driver
int
main()
{
int a[] = { 17, 3, 16, 5, 14, 8, 10, 7, 15, 1, 13, 4, 9, 12, 11, 6, 2 };
size_t n = sizeof(a) / sizeof(a[0]);
merge_sort(a, n);
print_array(a, n);
return 0;
} // main
Antwoord 9
Gebruikmakend van C++ std::inplace_merge, kan in-place merge sort als volgt worden geïmplementeerd:
template< class _Type >
inline void merge_sort_inplace(_Type* src, size_t l, size_t r)
{
if (r <= l) return;
size_t m = l + ( r - l ) / 2; // computes the average without overflow
merge_sort_inplace(src, l, m);
merge_sort_inplace(src, m + 1, r);
std::inplace_merge(src + l, src + m + 1, src + r + 1);
}
Meer sorteeralgoritmen, waaronder parallelle implementaties, zijn beschikbaar in https://github.com/DragonSpit/ParallelAlgorithmsrepo, die open source en gratis is.
Antwoord 10
Ik heb zojuist het merge-algoritme geprobeerd voor merge-sort in JAVAmet behulp van het insertion-sort-algoritme, met behulp van de volgende stappen.
1) Er zijn twee gesorteerde arrays beschikbaar.
2) Vergelijk de eerste waarden van elke array; en plaats de kleinste waarde in de eerste array.
3) Plaats de grotere waarde in de tweede array met behulp van invoegsortering (van links naar rechts doorlopen).
4) Vergelijk dan opnieuw de tweede waarde van de eerste array en de eerste waarde van de tweede array, en doe hetzelfde. Maar als er wordt geruild, is er een aanwijzing om de andere items over te slaan, maar alleen ruilen is vereist.
Ik heb hier wat optimalisaties aangebracht; om kleinere vergelijkingen in invoegsortering te houden.
Het enige nadeel dat ik bij deze oplossing heb gevonden, is dat er grotere verwisseling van array-elementen in de tweede array nodig is.
bijv.)
Eerste___Array: 3, 7, 8, 9
Tweede array: 1, 2, 4, 5
Vervolgens zorgt 7, 8, 9 ervoor dat de tweede array elke keer alle elementen met één verwisselt (naar links verplaatst) om zichzelf in de laatste te plaatsen.
Dus de veronderstelling hier is dat het verwisselen van items verwaarloosbaar is in vergelijking met het vergelijken van twee items.
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;
}
}