List processing: sort again, naturally

ABSTRACT

This paper discusses a possible student project for use within the Data Structures and Algorithms treatment of linked lists. Students can explicitly compare the recursive list-oriented MergeSort algorithm with iterative list-oriented MergeSort algorithms (with O(n) space overhead) including the "Natural MergeSort." The author's experimental results are shown for implementations in C and in Java.

REFERENCES

• 1: Sedgewick, Robert. Algorithms in C; Parts 1-4. Third edition: Addison, Wesley, 1998.
• 2: Robert Sedgewick , Michael Schidlowsky, Algorithms in Java, Part 5: Graph Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2003
• 3: Sartaj Sahni, Data Structures, Algorithms, and Applications in C++, McGraw-Hill Pub. Co., 1999
• 4: Mordecai J. Golin , Robert Sedgewick, Queue-mergesort, Information Processing Letters, v.48 n.5, p.253-259, Dec. 10, 1993 [doi>10.1016/0020-0190(93)90088-Q]
• 5: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 6: Proof provided by Dr. Ray Hamel of my department: There are on average (n-1)/2 sequence breaks in a sequence of n randomly selected distinct items. Each sequence S of n items {where S = (S1, . . ., Sn)} has its reverse sequence R such that Rj = Sn-j+1. Both sequences together have n-1 sequence breaks: for each adjacent pair of (distinct) values, the two values are out of order either in R or in S (but not in both), and there are n-1 adjacent pairs. For randomly selected sequences, both sets are equally likely, so that there are (n-1)/2 sequence breaks on average.
• 7: Rolfe, Timothy. "Algorithm Alley: Randomized Shuffling", Dr. Dobb's Journal, Vol. 25, No. 1 (January 2000), pp. 113--14.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Lists, stacks, and queues

Additional Classification:
  E. Data
  E.5 FILES
      Subjects: Sorting/searching

General Terms:
Algorithms, Design, Theory

Keywords:
mergesort, naturalmerge, sorting