Slide 8.8: Internal sorting

Internal Sorting

If a sorting algorithm were applied directly to data stored on a disk, it is clear there would be a lot of jumping around, seeking, and rereading of data. This would be a very slow operation—unthinkably slow.

Internal sort is to read entire file from the disk into memory and then do the sorting there. However, binary searching and internal sorting have the following limitations:

Binary searching requires more than one or two accesses. Ideally, we would like to approach RRN retrieval performance (one access) while still maintaining the advantages of access by key.
Keeping a file sorted is very expensive.
An internal sort works only on small files.

Chapter 8 will introduce some advanced sorting algorithms; this chapter introduces a simple sorting algorithm: a keysort, which is a variation on internal sorting and avoids the sorting of records in a file. The following interface tries to keysort a fixed-length-record file whose format is shown in the following example. It is the same as the one used in a binary search.

10    85   
File Structures: An Object-Oriented Approach with C++|0201874016|94.80|360|         
Learning WML & WMLScript|1565929470|17.48|12|                                       
XML in a Nutshell, 2nd Edition|0596002920|39.95|39|                                 
Java and XSLT|0596001436|26.37|890|                                                 
WAP Servlets: Developing Dynamic Web Content With Java and WML|047139307|32.99|4|   
WAP Development with WML and WMLScript|0672319462|18.99|56|                         
Advances in Security and Payment Methods for Mobile Commerce|1591403456|89.95|182|  
M Commerce: Technologies, Services, and Business Models|0471135852|23.09|5|         
Mobile Commerce|0521797561|29.51|93|                                                
Dynamic WAP Application Development|1930110081|34.59|18|

Enter a URL to Keysort the File by ISBN.
URL:	Help Show file content Sort (keysort) Sort (Unix)
Password: