7,847 views
6 votes
6 votes

What is the best sorting algorithm to use for the elements in array are more than 1 million in general?

A

Merge sort.

B

Bubble sort.

C

Quick sort.

D

Insertion sort.

 Ans:C

Source: http://quiz.geeksforgeeks.org/algorithms-insertionsort-question-6/

You have to sort 1 GB of data with only 100 MB of available main memory. Which sorting technique will be most appropriate?

A

Heap sort

B

Merge sort

C

Quick sort

D

Insertion sort

Ans: B

Source: http://quiz.geeksforgeeks.org/algorithms-searching-and-sorting-question-16/

Kindly explain on why the answers are different?

1 Answer

2 votes
2 votes

In first question, we have information how the data is represented while in second question we have information that data can't fit into main memory.

In first question, data is stored in array, so quick sort will be better option than merge sort because quick sort has good locality of reference on the other hand merge sort might be slow because it require extra memory to sort.Therefore quick sort is best algorithm for sorting in this case.

In second question,data can't fit into main memory because of less availability of main memory,so we need some external sorting algorithm(outplace) that is merge sort.

Related questions

0 votes
0 votes
2 answers
2
_Madhuri asked Oct 9, 2021
634 views
The complexity of comparison based sorting algorithm is (nlogn) .How?
0 votes
0 votes
0 answers
3
1 votes
1 votes
2 answers
4
Ravi Dubey asked Aug 2, 2018
829 views
Could a binary search tree be built using o(n lg n) comparisons in the comparisonmodel? Explain why or why not.