Past exam question: 2065 Shrawan (Regular / Back), Q7
Open in the Padhaiko appQuestion
What is internal and external sorting? Write an algorithm for shell sort.
Solution
Internal vs. External Sorting:
- Internal Sorting: Sorts data completely within main memory (RAM) with random element access (Quick, Merge, Heap, Insertion sort).
- External Sorting: Sorts data too large for RAM by reading/writing chunks on disk (External -way Merge Sort).
Algorithm for Shell Sort:
Algorithm SHELL_SORT(A, n):
1. gap = floor(n / 2)
2. While gap > 0:
For i = gap to n - 1:
temp = A[i]
j = i
While j >= gap and A[j - gap] > temp:
A[j] = A[j - gap]
j = j - gap
A[j] = temp
gap = floor(gap / 2)Answer:
Internal sorting operates inside RAM; external sorting handles disk-resident data exceeding RAM. Shell sort runs gapped insertion passes with gap halving from down to 1.