Yes, this solution is very slow, but during solving this problem new type of sorting was invented, which sorts any massive in O(n*log(n)) time and doesn't require additional memory!

I think you should first read "The art of computer programming" by Donald E. Knuth (especially, Volume 3 "Sorting and Searching") and "Introduction to Algorithms", the MIT Press...

Why is your solution so slow? My program works O(N*log(N)) too (using Qsort) but in 0.046 sec.

There are lots of sorts of sorting methods can do this(nlogn at any time) and faster than you.

Please, send me your code - dkorduban[at]ukr.net

Edited by author 25.03.2005 19:49

I am giving my apologizing because I accidentally mislead everybody. I used silly Binary Search method to solve this problem. I've written the first lines because I contrived
this method myself during solving this problem, so I was
very pleased and wrote the strings at the beginning in the
heat of the solvation of the problems.

To <Dmitry 'Diman_YES' Kovalioff>: I've did't expect that
books of so kind even exists at that time, not mentioned
that I read one of them. You've opened my eyes. Thank You
very much for this.
To everyone who wants see my code (Pascal):
{In reading we trying to place the last read element into
 the massive of the last M read elements in the proper place
 following the value of it. So the last element in this
 massive will be the greatest - we write this element to the
 ouput.}
const
 lenmax=100000;
 upbone=100000;
var
 elkol: array [0..upbone] of word;
 elems, elist: array [1..lenmax] of longint;
 curno, curelem, m, els, elpos: longint;
 already_in_list: boolean;
function BinSearch(bsx: longint): longint;
var
 bsp, bsq, bsi: longint;
begin
 bsp:=1;  { Left border of the search  }
 bsq:=els;  { Right border of the search }
  while bsp <= bsq do
   begin
    bsi:=(bsp + bsq) div 2;
     if elist[bsi] = bsx then
      begin
       BinSearch := bsi;
       already_in_list:=true;
       exit
      end;
     if bsx < elist[bsi] then
       bsq := bsi - 1
     else
       bsp := bsi + 1
   end;
  if bsx>elist[bsq] then
    BinSearch:=bsp
  else
    BinSearch:=bsq;
 already_in_list:=false
end;
procedure ins_new_item;
begin
  if curelem<elist[1] then
   begin
    move(elist[1], elist[2], els*4);
    elist[1]:=curelem;
    inc(els)
   end
  else
     if curelem>elist[els] then
      begin
       inc(els);
       elist[els]:=curelem;
      end
     else
      begin
       elpos:=binsearch(curelem);
        if not already_in_list then
         begin
          move(elist[elpos], elist[elpos+1], (els-elpos+1)*4);
          elist[elpos]:=curelem;
          inc(els)
         end
      end
end;
begin
 fillchar(elkol, sizeof(elkol), 0);
 readln(m);
 readln(curelem);
  if curelem=-1 then
    exit;
 elist[1]:=curelem;
 els:=1;
 curno:=0;
  while (curno<m) and (curelem<>-1) do
   begin
    inc(curno);
    elems[curno]:=curelem;
    inc(elkol[curelem]);
     if curno>1 then
       ins_new_item;
    readln(curelem)
   end;
{First M or less elements are being read}
 writeln(elist[els]);
  if curelem=-1 then
    exit;
{If not end of sequence, reading until curelem=-1
 (condition of the end of the sequence)}
  while curelem<>-1 do
   begin
    inc(curno);
    elems[curno]:=curelem;
    inc(elkol[curelem]);
    ins_new_item;
    dec(elkol[elems[curno-m]]);
     if elkol[elems[curno-m]]=0 then
      begin
       elpos:=binsearch(elems[curno-m]);
       move(elist[elpos+1], elist[elpos], (els-elpos)*4);
       dec(els)
      end;
    writeln(elist[els]);
    readln(curelem)
   end
end.