Cod sursa(job #2747578)

Utilizator TeodorLuchianovTeo Luchianov TeodorLuchianov Data 29 aprilie 2021 14:04:05
Problema Sortare prin comparare Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <string>
#include <sstream>

using namespace std;

ifstream in("algsort.in");
ofstream out("algsort.out");

int const NMAX = 500000;
int arr[1 + NMAX], n;
int narr[1 + NMAX];

void computeMerge(int from, int to){
  if(from >= to){
    return;
  }else{
    int mid = (from + to) / 2;
    computeMerge(from, mid);
    computeMerge(mid+1, to);
    int a = from, b = mid+1, i = 0;
    while(a <= mid || b <= to){
      if(a > mid){
        i++;
        narr[i] = arr[b];
        b++;
      }else if(b > to){
        i++;
        narr[i] = arr[a];
        a++;
      }else{
        if(arr[a] < arr[b]){
          i++;
          narr[i] = arr[a];
          a++;
        }else{
          i++;
          narr[i] = arr[b];
          b++;
        }
      }
    }
    for(int j = 1;j <= i;j++){
      arr[from + j - 1] = narr[j];
      //cout << narr[j] << ' ';
    }
    //cout << '\n';
  }
}

int main() {

  stringstream ss;
  string s;
  int c;
  getline(in, s);
  getline(in, s);
  ss << s;
  while(ss >> c){
    n++;
    arr[n] = c;
  }
  computeMerge(1, n);
  for(int i = 1;i <= n;i++){
    out << arr[i] << ' ';
  }
  return 0;
}