What’s the difference between External vs Internal sorting?

Technology CommunityCategory: SortingWhat’s the difference between External vs Internal sorting?
VietMX Staff asked 3 years ago
  • In internal sorting all the data to sort is stored in memory at all times while sorting is in progress.
  • In external sorting data is stored outside memory (like on disk) and only loaded into memory in small chunks. External sorting is usually applied in cases when data can’t fit into memory entirely.

So in internal sorting you can do something like shell sort – just access whatever array elements you want at whatever moment you want. You can’t do that in external sorting – the array is not entirely in memory, so you can’t just randomly access any element in memory and accessing it randomly on disk is usually extremely slow. The external sorting algorithm has to deal with loading and unloading chunks of data in optimal manner.

Divide and conquer algorithms like merge sort are commonly used for external sorting, because they break up the problem of sorting everything into a series of smaller sorts on chunks at a time. It doesn’t require random access to the the dataset and can be made to operate in chunks which fit in memory. In some cases the in-memory chunks maybe sorted using an in-memory (internal) sorting algorithm.