PadhaikoAll subjects

Past exam question: 2079 Ashwin (Back), Q8(a)

Data Structure and Algorithms · 2 marks

Open in the Padhaiko app

Topic: Sorting Algorithms

Question

Differentiate internal and external sorting.

Solution

Conceptual Distinction: Sorting algorithms are classified as internal or external based on the location of the dataset during the sorting process and the primary memory constraints of the system.

Comprehensive Comparison Matrix:

ParameterInternal SortingExternal Sorting
Storage MediumPrimary Memory (RAM only).Secondary Storage (Disk/SSD) assisted by small RAM buffers.
Data SizeFits entirely within physical RAM ().Exceeds physical RAM capacity ().
Speed & BottleneckExtremely fast; CPU-bound (number of key comparisons and memory swaps).Significantly slower; I/O-bound (number of disk block reads and writes).
Data Access ModeDirect, high-speed random access ( pointer/index access).Sequential block/page access subject to disk seek time and transfer rate.
Core AlgorithmsQuick Sort, Merge Sort, Heap Sort, Insertion Sort, Bubble Sort.Multiway External Merge Sort, Replacement Selection, Polyphase Merge.
Auxiliary BufferingRequires minimal auxiliary arrays (or in-place extra memory).Requires specialized input/output RAM page buffers to sort and merge runs.
Answer:

All past exam questions for Data Structure and Algorithms