Without a sample document and a precise step by step instruction we can't do anything here.

Created attachment 48727 [details]
Source file

Created attachment 48728 [details]
Sorted file

The Turkish locale was used.

As for instruction: open, select all, sort, save.

@Urmas:
No idea what writer sort function you are talking about. We would save much time if you would invest some more care.

There's ONLY ONE sort command, in Tools menu, called Sort.

Are you trolling me or what?

Urmas, you should not expect people to know the menus by heart. It is in your own interest to make it as easy as possible for people to reproduce your problem. (If you want the problem to be fixed, that is.) Being rude and argumentative is not helpful. Please note that many people (like Rainer) are trying to help you on their own time, just out of friendliness.

I checked the document again and can confirm sort problems, it seems that the first few hundred pages will be sorted correctly then (for me starting with line 14465) sort order becomes messed up. 

But currently I do not understand all details of the problem: 
for example when I copy / paste the complete documents I would await to see always 2 identical lines sequenced, what does not happen. 

Sorting source document with CALC (UTF8), opening sorted document with WRITR (UTF8) and doing a new sort will mess up sort order,
 first lines üiiuşeıüük, uiiwoyrmür, üiizpesyho
 line 14463ff zzyjebojbq, zzywrutjft, aaalörmpdö, aaamljmgzç
 further lines sorted correctly until uiittüqzvl

Same problems with OOo 3.4-dev, OOo3.1.1, OOo 1.1.4, always in line 14465 the sort order breaks. Some internal "during process update" problem?

CALC will sort that document (opened as utf8-csv without problems.

I will do further tests in the evening (for example whether line / word  length has influence) before I will assign.

@Urmas
Only for the sake of completeness (I doubt that that's related to the problem):
- caracter set in source document is utf8?
- May be some information how you created the document might be useful.
- With what codepage / character set did you open the document?
- What were your settings in the sort dialog?

Here the results of some further tests.

1. Magic line number 14465
I used calc to create a text document with longer words, and during
creation I used "Fill down", what broke in row 14465 in the first attempt 
(whatever that might mean) fill down from row 14465 ... 80000 then
worked without problems. That looks similar to my results with a pre-
sorted WRITER document in comment 8, where a break was at line 14465 and 
further contents has been sorted correctly, but that also might be magic and not a real relation ;-)

2. Sort with much longer words
In my experiment from 1. I added string "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" to all lines of reporter's sample. Sort with same result, sort messed up beginning with line 14465. So it seems not to be a general overload, missing RAM or similar problem-

3. Sort Text document with numbers
I created a text with sorted lines with numbers 1 ... 80.000
As expected sort order became broken.
- First line 65537 (what is (2^16) +1)
- sort correct until 14464
- Start with 1 from line 14465
- Last line contents 65536 (2^16)

4. Test like 3., but with 81000 lines
- First line 65537 (what is (2^16) +1)  (as above)
- sort correct until 15464   (1000 later as in 3.)
- Last line contents 65536 (2^16)

What ever that all might mean!

Currently I see this one as a minor problem, sorting quintillions of lines is not a really normal Word Processor application. But of course, it's strange and a bug.

@Cédric
Please feel free to reassign if it's not your area

Since all new unconfirmed bugs start in state UNCONFIRMED now and old unconfirmed bugs were moved to NEEDINFO with a explanatory comment, all bugs promoted above those bug states to NEW and later are automatically confirmed making the CONFIRMED whiteboard status redundant. Thus it will be removed.

Apparently is not reproducible in 4.0.3.