List-based MergSort Example
(Bryan Flamig; $0) is the C++ source
code that shows a way to sort
singly-linked lists, using a
non-recursive merge sort algorithm.

List-based MergSort Example
(Bryan Flamig; $0) is the C++ source
code that shows a way to sort
singly-linked lists, using a
non-recursive merge sort algorithm.



List-based MergeSort Example
from the upcoming book
Practical Algorithms in C++

README FILE

Copyright(c) 1993 Azarona Software
All rights reserved.

August 28, 1993

INTRODUCTION
============

The included files show a way to sort singly-linked lists, using a
non-recursive merge sort algorithm. The code is part of the upcoming
book "Practical Algorithms in C++", by Bryan Flamig.

The algorithm used is reminiscent of external sorting algorithms
normally used to sort files. The basic idea is to first split the
list in half, and then merge-sort the nodes in blocks, first with
block sizes of 1, then 2, then 4, and so on until the list is sorted.
To do this, 4 working lists are used, divided into two groups. At
any one time, one of the groups will be used for input, the other
two for output. The sorting is finished when there is only one output
list. Here is an example:

Original list: [DOGZILLAGOESTOTHEMOUNTAINS]

Split list in half, alternating between two output lists:

list 1: [DGILGETTEONAN]
list 2: [OZLAOSOHMUTIS]

1st pass: Merge 1-blocks into 2-blocks, sort in process

list 3: [DO IL GO OT EM NT NS]
list 4: [GZ AL ES HT OU AI]

2nd pass: Merge 2-blocks into 4-blocks, sort in process

list 1: [DOGZ GEOS EMOU NS]
list 2: [AILL HOTT AINT]

3rd pass: Merge 4-blocks into 8-blocks, sort in process

list 3: [ADGILLOZ AEIMNOTU]
list 4: [EGHOOSTT NS]

4th pass: Merge 8-blocks into 16-blocks, sort in process

list 1: [ADEGGHILLOOOSTTZ]
list 2: [AEIMNNOSTU]

5th pass: Merge 16-blocks into 32-blocks

list 3: [AADEEGGHIILLMNNOOOOSSTTTUZ]
list 4: []

We're done! List 3 contains the result.

Each pass does approximately n/2 comparisons, (sometimes less)
where n is the length of the list, and there will be logn passes,
thus this is a O(nlogn) sort. Also, this sort is stable as well,
(meaning that if two keys are identical, they will have the same
relative positions in the sorted list as they had in the unsorted
list.)

On a 33Mhz 486 machine, this routine can sort a list of 30,000
integer nodes in 1 second!


OTHER MERGE SORT ALGORITHMS
===========================

There are other books that show the merge sort algorithm for
linked lists, both recursively and non-recursively. However, in
all of the books this author has seen, the process of splitting
the list into two in order to do the merging is done in a rather
naive way, scanning down the list looking for the "middle" in
order to split the list in two. This is quite wasteful.

Surprisingly, some of these same books show, in later chapters,
techniques for doing external sorting, that if applied to linked
lists, would do away with the wasteful scanning to find the
midpoint! The technique used for external sorting is what I used
to implement the linked-list merge sort algorithm given here.


TYPE OF LISTS SORTED
====================

The code as given here sorts singly-linked lists that are
null-terminated and have no headers. I did this because
most people will understand that type of list. The nodes
of the list are assumed to hold data of type Item, and
Item is assumed to have the appropriate comparison operators
defined. (For ascending sorts, we use <=, for descending,
>= is used.) NOTE THAT YOU MUST USE <= or >= and not < or >,
otherwise, the sort will not be stable.

This sort routine can be templated quite easily, as you might
surmise. Also, it's possible to make slight modifications to
the routine to make it work for circular singly-linked lists
that have dummy headers, for example, the Slist template class
as given in the companion book "Practical Data Structures in
C++". Here is a sketch of the necessary changes. (We show the
code here in template form):

template
void MergeSort(Slist &v)
{
// Check for empty or one-node list
if (v.IsHeader(v.Front()) || v.IsHeader(v.Front()->Next())) return;

v.CircularToNullTerm(); // Convert to null-terminated form

// Rest of merge-sort algorithm up to last statement as before,
// except use Snode.

// At this point, p points to first node of sorted list, r
// points to the last node. Convert back to circular list.

v.NullTermToCircular(p, r);
}

If you examine the MergeSort() routine, you'll notice there is only
one statement that relies on the type of data in the node: the single
comparison during merging. If you use the Slist class, along with
it's dataless Slistb base class, it's possible to write the MergeSort()
routine as a non-templated class that works for the whole family of
Slist classes. Simply use Slistb and Snodeb (these are dataless),
instead of Slist and Snode. Then pass in a pointer to
the function to use for comparison, for your type of nodes. For
example:

void MergeSort(Slistb &sl, int (*Compare)(Snodeb *a, Snodeb *b))
{
... Use Slistb and Snodeb throughout ...
}

For lists holding integers, the Compare() function might be coded
as follows:

int IntLessThan(Snodeb *a, Snodeb *b)
{
return ((Snode *)a)->info - ((Snode *)b)->info;
}

Slist sl;
...
MergeSort(sl, IntLessThan);

Although this elegantly reuses the MergeSort() code for all
Slist list's, having to use a pointer to the Compare()
function rather than doing a simple comparison operator may
slow down the algorithm by as much as 50% for lists holding
simple integers. Of course, if you have to use an overloaded
comparison operator function for your type of data anyway,
then you may not see much performance drop.


COPYRIGHTED SOFTWARE
====================

The source code is copyrighted by Azarona Software, but I'm
providing it to you free of charge. You are free to experiment
with the code, include compiled versions of it in your own
applications, personal or commercial. HOWEVER, YOU MAY NOT
DISTRIBUTE THE SOURCE CODE FOR A PROFIT OR FEE OF ANY KIND
WITHOUT THE EXPRESS WRITTEN PERMISSION OF AZARONA SOFTWARE.

You are granted permission to give away the source code to
friends, upload the files to a BBS, etc., AS LONG AS NO FEE
IS CHARGED FOR THE SOFTWARE, AND AS LONG AS THE FILES ARE
DISTRIBUTED EXACTLY AS GIVEN HERE, WITH THE SAME FILE NAMES,
THE SAME NUMBER OF FILES, AND THE COPYRIGHT NOTICES INTACT.
You may "zip" the files into a single-file archive, if you wish.


PRACTICAL ALGORITHMS IN C++ BOOK
================================

This is the companion volume to the "Practical Data Structures in
C++" book, due in the Spring of 1994. While I can't say for certain
exactly what will be covered in this book, here is a list of
possible candidate topics:

* Sorting (insertion, shell, heap, quick, merge, external)
* Hashing (closed and open), creating symbol tables
* Priority queues as heaps
* Graphs, including algorithms for depth-first, breadth-first,
best-first, (A*-algorithms), topological sorting, etc.
* Randon number generation, including array shuffling, and
taking random samples from known and unknown population sizes
* String searching, such as Boyer-Moore-Horspool, and others
* Finite automata machines
* Recursive descent parsing
* Regular expression matching
* Compression, including huffman and sliding-window dictionaries
* Simultaneous equation solving using LU matrix decomposition


PRACTICAL DATA STRUCTURES IN C++ BOOK
=====================================

Practical Data Structures in C++
Author: Bryan Flamig
Publisher: John Wiley & Sons
ISBN 0-471-55863-X

This book retails for $42.95, and includes a code disk, packed with
over a megabyte of source code. Subjects covered are dynamic arrays,
smart pointers, reference counting, strings, vectors, matrices,
linked lists, stacks, queues, binary trees, splay trees, red-black
trees, file-based objects, caching, and B-trees. The book is based
heavily on templates, and includes some useful C++ tricks. The
book is for intermediate to advanced C++ programmers.

Unlike most data structures books, this book focuses on giving
you complete code, and complete techniques. For instance, many
books talk about red-black trees and splay trees, but very few
show you how to delete nodes from these trees! This book does.
Also, many books give lip service to B-trees, but few books
actually give you the code for them, and amazingly, few books
implement them for disk-based trees, which is curious, since
B-trees were designed with disk-based trees in mind!

Also, most data structures books currently on the market were
written for Pascal, or worse, written in pseudo-code. This
book, in contrast, was written specifically for C++, and exploits
the capabilities of C++ to the fullest. You won't find any vague
pseudo-code here.


COMPILER USED
=============

This code was developed using BC++ 3.1, and hasn't been tried
with other compilers, although I don't anticipate any troubles.


PACKING LIST
============

MERGSORT.CPP Merge sort testing program
MERGSORT.PRJ BC++ 3.1 project file for testing program
README This readme file


ABOUT THE AUTHOR
================

Bryan Flamig is a software developer and consultant specializing in
C++ programming. He is the author of numerous books, including the
popular "Turbo C++: Step by Step", and coauthor of "Object-Oriented
Programming with Turbo C++", and of course, the author of "Practical
Data Structures in C++", all published by John Wiley & Sons.

Besides consulting and writing books, Bryan also gives training
seminars focusing on C++. You may reach Bryan at:

Azarona Software
P.O. Box 768
Conifer, CO 80433

(303) 697-1728 Fax
73057,3172 CompuServe