Problem przy sortowaniu

Witam :)

Chciałbym się dowiedzieć czy dobrze rozumiem ideę MergeSort.

Weźmy sobie dowolny zbiór A który będzie wartościowany następująco: A={ 5,2,4,6,1,3,2,6} jest to zbiór 8-elementowy.

W myśl MargeSort po podzieleniu A/2 mamy dwa podzbiory 4 -elementowe nazwijmy je X oraz Y. X={ 5,2,4,6} i Y={ 1,3,2,6} weźmy również jakiś zbiór Z do którego będziemy wrzucać wyniki zatem porównujemy kolejno np 5 z 1 i nasza liczba 1 trafia do zbioru Z potem 5 z 3 i 3 trafia do Z...taki jest aż do porównania z liczbą 6 potem kolejno ze zbioru X również są przepisywane do zbioru Z do momentu 6=6 po tym zbiory się zerują i Z={ 1,3,2,5,2,4,6,6} i właśnie nie jest to posortowany ciąg czy mógłby ktoś powiedzieć mi o czym może zapomniałem czy też może źle to robię?

W zasadzie nic tu nie jest poprawnie. Pominąłes najważniejszy krok: SORTUJEMY podzbiory przed ich scalaniem!

1. Podziały na podzbiory następują aż dojdziemy do podzbiorów 1 elementowych.
2. Algorytm działa tak: dzielimy zbiór na 2 podzbiory, sortujemy je merge sortem, nastepnie te 2 posortowane podzbiory łączymy na zasadzie przepisywania do zbioru Z za każdym razem porównując "głowy" obu zbiorów żeby wiedzieć który teraz przerzucać.
   czyli w twoim przypadku mamy zbiór A={ 5,2,4,6,1,3,2,6}
   dzielimy go na X={5,2,4,6} i Y={1,3,2,6}
   sortujemy podzbiory więc mamy X={2,4,5,6} i Y={1,2,3,6}
   Teraz łączymy podzbiory na zasadzie: przepisujemy do zbioru Z zawsze najmniejszy element z obu podzbiorów więc mamy:
   X={2,4,5,6} i Y={1,2,3,6} Z={}
   X={2,4,5,6} i Y={2,3,6} Z={1}
   X={4,5,6} i Y={1,2,3,6} Z={1,2}
   X={4,5,6} i Y={3,6} Z={1,2,2}
   X={4,5,6} i Y={6} Z={1,2,2,3}
   itd aż do wynikowego zbioru
   X={}, Y={}, Z={1,2,2,3,4,5,6,6}

Oczywiście możesz zapytać: "JAK sortujemy te dwa podzbiory?!" Odpowiedź jest prosta: merge sortem :P Zobacz co się dzieje na najniższym poziomie, kiedy mamy zbiór 2 elementowy:
zbiór={2,4}
X={2}, Y={4}
nie ma już co dzielić, więc łączymy pozbiory tak samo jak wyżej, porównując który ma mniejszą "głowę"
X={2}, Y={4}, Z={}
X={}, Y={4}, Z={2}
X={}, Y={}, Z={2,4}
i voila, podzbiór posortowany.

Rozumiem...czyli taki kod w C++ mógłby załatwić dzielenie na /2 i sort?

void merge(int array[], int start, int middle, int end) 
{

int *array_pom = new int[(end - start)];// utworzenie tablicy pomocniczej
      int i = start, j = middle + 1, k = 0;
 
             while (i <= middle && j <= end) 
               {
                  if (array[j] < array[i]) 
                      {
                         array_pom[k] = array[j];
                                  j++;
                      }
                  else 
                      {
                       array_pom[k] = array[i];
                                 i++; 
                      }
                                k++;
}

Biorąc powyższy przykład działało by to tak:

A={ 5,2,4,6|1,3,2,6} | <--środek

array [j]=2<= array [i]=5
array [j]=4<= array [i]=5
array [j]=5<= array [i]=6
array [j]=3<= array [i]=1
array [j]=2<= array [i]=3
array [j]=6<= array [i]=3
następnie do array_pom = {2,4,5,6 |1,2,3,6}

I w sumie mamy te 2 podzbiory posortowane jak mówiłeś...

Nie sprawdzałem czy kod jest całkiem poprawny, ale koncepcyjnie jest ok, o to właśnie chodzi.
Ciekawostka: da się zrobić merge w miejscu (bez alokacji dodatkowej tablicy) ale jest to dość skomplikowane ;)

A czy mógłby ktoś sprawdzić kod? Bo właśnie muszę zakodzić takie sortowanie pierw musiałem poznać na czym to polega a teraz kombinuję z kodzeniem.

No wygląda mniej więcej ok, ale musisz na koniec przepisać dane z tablicy pomocniczej do tej właściwej.

A jeszcze się zapytam bo wiem,że tym kodem dojdę do takiej postaci tablicy A={2,4,5,6 |1,2,3,6}} czy ta funkcja od razu załatwia mi również porównania tak jak mówiłeś czyli teraz np 2 z 1 potem 2 z 2 itp az do momentu otrzymania tablicy_pom={1,2,2,3,4,5,6,6} ??

Powoli. Ten kod który pokazałeż to sama procedura łączenia dwóch posortowanych podzbiorów. Musisz jeszcze dopisać procedurę mergeSort() która dla podzbiorów liczniejszych od 1 elementowych dokonuje podziału, woła samą siebie na podzielonych podzbiorach a potem scala, a dla podzbiorów o liczności 1 dokonuje tylko ich scalenia.

void merge_sort(int tablica[], int start, int koniec) 
{
       int srodek;
 
           if (start ! = koniec)
             {
                 srodek = (start + koniec) / 2;
                 merge_sort(tablica, start, srodek);
                 merge_sort(tablica, srodek + 1, koniec);
                 merge(tablica, start, srodek, koniec);
             }
}

Ja bym to zrobił w ten sposób i od razu chyba by mi to dzieliło tak jak mówiłeś do pojedynczych elementów nastepnie by scalało i porównywało ze sobą?

Powinno chyba być ok (tylko jeszcze przypisanie wlasciwej tablicy elementow z pomocniczej) bo bedzie on rozbijam jak juz mamy podzielone na 2 czesci to on bedzie je nadal rozbijal do pojedynczych elementow i kolejno bedzie porownywal juz w merge i z j czyli jak wyzej mielismy jako pojedynczy 7 5 to scalamy to porownujemy i zapisujemy do tablicy pomocniczej jako element 5,7 i jak np dodjamey do tego pojedynczy element np 6 to bierze on 6 jako j-ty element i porownuje z i-tym czyli i z 5 i z 7 i umieszcza go odpowiednio i tak dalej...czy dobry mam tak rozumowania?