#include <iostream>
using namespace std;
int a[100], tb[100], n;
void merge(int left, int middle, int right)
{ int pos1 = left;
int pos2 = middle + 1;
int k = pos1;
while (pos1 <= middle && pos2 <= right)
{ if (a[pos1] <= a[pos2]) { tb[k] = a[pos1]; pos1++; }
else { tb[k] = a[pos2]; pos2++; }
k++;
}
while (pos1 <= middle)
{ tb[k] = a[pos1]; pos1++; k++; }
while (pos2 <= right)
{ tb[k] = a[pos2]; pos2++; k++; }
for (int j = left; j <= right; j++) a[j] = tb[j];
}
void mergeSort(int left, int right)
{ int middle = (left + right) / 2;
if (left < middle) mergeSort(left, middle);
if (middle+1 < right) mergeSort(middle+1, right);
merge(left, middle, right);
}
void printtab()
{ for (int i = 1; i <= n; i++) cout << a[i]<<" ";
cout << endl;
}
int main()
{ cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
printtab();
mergeSort(1, n);
printtab();
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
int a[20];
int n = 20, tmp;
void printa(int k)
{
for (int i = 0; i < k; i++) printf("%4d", a[i]);
printf("\n");
}
int indexmaxchild(int h)
{
if (a[2 * h + 1] > a[2 * h + 2]) return 2 * h + 1; else return 2 * h + 2;
}
int main()
{
// generate numbers
srand(time(NULL));
for (int i = 0; i < n; i++) a[i] = rand() % 100;
printa(n);
// creare max heap
for (int i = 1; i < n - 2; i++)
{
// pun in heap a[i]
int h = i; // pornim din radacina
while (h > 0 && a[h] > a[(h - 1) / 2])
{
tmp = a[h]; a[h] = a[(h - 1) / 2]; a[(h - 1) / 2] = tmp;
h = (h - 1) / 2;
}
printa(i+1);
}
// transformare in tablou sortat
int k = n - 1, ifmax;
for (int i = 0; i < n; i++)
{
// move head to the end of heap
tmp = a[0]; a[0] = a[k]; a[k] = tmp;
k--; // remove from heap
int h = 0;
ifmax = indexmaxchild(h);
while(a[h] < a[ifmax] && ifmax <= k)
{
int tmp = a[h]; a[h] = a[ifmax]; a[ifmax] = tmp;
h = ifmax; ifmax = indexmaxchild(h);
}
printa(n);
// restore heap
}
// ultimele 2 elemente - reordonare la necesitate
if (a[0] > a[1]) tmp = a[0], a[0] = a[1], a[1] = tmp;
printa(n);
return 0;
}