CODEWITHSUNDEEP
algorithmsortingexternal-sortingonline-algorithm
user2698544
user2698544

Reputation: 59

What is the difference between an online sorting algorithm and an external sorting algorithm?

What is the difference between online sorting algorithm and external sorting algorithm ? Are they same or different?

Upvotes: 1

Views: 3658

Answers (1)

templatetypedef
templatetypedef

Reputation: 373452

An online sorting algorithm is one that will work if the elements to be sorted are provided one at a time with the understanding that the algorithm must keep the sequence sorted as more and more elements are added in. Algorithms that assume that the entire input will be given in advance, such as heapsort, will not work as online algorithms because they presume that they know all the elements in advance. On the other hand, an algorithm like insertion sort is online, since it purely works from the left to the right and doesn't need to see the entire array as it's working until it tries to process the very last element.

An external sorting algorithm is one where the goal is to sort data, typically provided in advance, that is so large that it cannot fit into main memory. While external sorting algorithms typically don't keep all the data to be sorted in memory at once, they usually assume that they can load any data that they need into memory at any time.

A good way of thinking about the difference is that in an online sorting algorithm, you should assume that you're trying to sort a sequence that is being generated dynamically - not all the data exists prior to the sort starting. In an external sorting algorithm, all the data already exists, but there's so much of it that you can't load everything into memory at once.

Hope this helps!

Upvotes: 7

Related Questions