Sorting Algorithms
elementary advanced
O(n2) O(n log n)
exchange quicksort
insert -->Shell O(n1.5)
selection heapsort
-- in situ - arrays
Shell
Shell == variable length insertion sort
External Sorting
files == sequence == strings
Mergesort
1. split file c into files at b
2. merge a and b (a run at a time) onto c
3. repeat 1 and 2 if # runs > 1
a: 25 38 || 59 73 84
c: 25 38 || 17 65 94 || 59 73 87 || 35 76
b: 17 65 94 || 35 76
c: 17 25 38 65 94 ||
35 59 73 76 87
Return to CIS 350 Index Page