In fact it can be said that they are the same for both external and internal use. It is likely that some algorithm is a little better in one case than other algorithms. I will not analyze one by one to reach that conclusion.
The choice of the most suitable algorithm depends on a number of factors. It is often said that the Quicksort is the most suitable for the general case. This does not mean that it is the best ever. It was created for use in RAM memory. But nothing prevents it from being used in secondary storage.
When going to secondary storage it is of utmost importance to access the disk as little as possible. So in theory you would need to find an algorithm that minimizes that, even if it has other higher costs.
But that is naive. In practice any classification algorithm that needs a lot of performance will combine different techniques to achieve the goal. It is obvious that one of these techniques is to put as much data as possible in memory and classify what gives there and go organizing all the portions. If I can get everything in the secondary memory into the primary, the best algorithm for that case will work well in memory. If you can’t put it all together, you need to manage the load as intelligently as possible. This has little to do with the algorithm of Sort in itself.
Note that the amount of memory that computers have today and the advent of SSD has greatly improved the condition of an algorithm not so optimized to achieve good results. If you have multiple processors the choice may tend more toward a specific algorithm that makes use of parallelism. In fact the proper hardware will make a lot of difference, probably more than the most suitable algorithm, as long as it doesn’t use a very bad one for any case.
You can do this transparently. You can use a memory Mapped file and do in memory everything you expect to do on file. The operating system manages what should be in memory and what needs to be on disk. This way you can focus on the algorithm and the memory management is on account of the operating system. Reading and writing is something you would have to do anyway. Of course it will be very efficient if you fit everything in memory or the data allow few page changes. Of course, this facility for having a cost, with the right algorithm can better control how you want to do paging, or can do much worse than the operating system would do. MMF is more used in computing than you think. All your executables are loaded into memory like this. All virtual memory works like this. In fact any memory allocation, in one way or another ends up calling an MMF.
If really the hardware is too restricted I remember that the Mergesort is usually good in cases like this. I’ve been doing some research and it seems that Bucketsort is even better, and has some variants that can better help each case. Has a study that seems to confirm this.
I think this may depend on each OS. Are you looking at any specific OS? (Windows, OS X, etc)
– Leonardo Pessoa
Actually no , I just want to know how to distinguish the ones that are used for each type same.
– stringnome