Re: Mergesort Vs Quicksort

Following up my previous post to make a correction or improvement:
I might not have correctly remembered my algorithm of months ago
for sorting records in an array using one auxilary (scratch) of the
same size and merge-sort as the basic algorithm. But never mind
because I think I have clarified the algorithm to be better anyway.
Here's the best new version of my two-array merge-sort algorithm:

Instead of a single recursive algorithm that writes the result
either into the *other* array or back to the same array depending
on how things turn out from lower levels of recursion, reporting to
call where the result happened to be, at the top level we have
control over whether the result will be back in the original array
(most commonly useful) or always to the other array (possible if
you want this behaviour for any perverse reason). As a result there
is a mode flag upon call of the algorithm that determines which of
the two behaviours will occur, or perhaps just two different
functions that are alternately mutually recursive. I'll describe
the algorithm as two separate functions, on the left side of the
diagram the output-back-in-same-array using aux for scratch only,
and on the right side of the diagram the source-to-other-array. At
the very start of either function we do a quick look-ahead to see
whether the number of records in the array segment to be sorted is
very small for special cases, or large enough for general
split/sortEach/merge algorithm. The following table tells what to
do in each case for the two mututally recursive functions:

in-place using-aux source-to-destination
+-------------------------------------------------------------------+
n=0 | |
| Do nothing. +--------------------------------------+
n=1 | | Move single record to destination. |
+----------------------------+--------------------------------------+
n=2 | Do nothing, or swap trick. | Merge from one array to other array. |
+----------------------------+--------------------------------------+
n>2 | General case: Split in half, |
| sort each half by calling *other* function, |
| merge from one array to other array. |
+-------------------------------------------------------------------+

The only case that needs further explanation is n=2 leftside:
Compare the two records. If they are already in correct sequence, do nothing,
else swap them in-place using whichever of these algorithms is fastest:
- Move smaller record from main array to aux array, in any
location that minimizes the number of page boundaries it
crosses, then slide (*) larger record to other end of main
array segment, then move smaller record back into main array
to fill hole in segment vacated by the slide.
- Use the modular permutation cycles algorithm I described in previous msg.

* (Caution for novices: Since the longer segment overlaps where it
was and where it will be moved to, you have to be careful which
direction you copy bytes to avoid overwriting a byte that hasn't
yet been copied to its new location. If it slides from left end
to right end, then you have to copy the rightmost byte first
then work leftward. But if it slides from right end to left end,
then you have to copy the leftmost byte first then move rightward.)

Note that Knuth's algorithm of reversing each part in-place then
reversing the concatenation in-place, or vice versa, is rejected
for sure, because it costs the most time but doesn't save any space
because we already have the second (aux) array allocated.

Reminder, calling convention (from earlier message) is clarified here:
- Starting (inclusive) index of segment to be sorted (for each function)
- Ending (exclusive) index of segment to be sorted (for each function)
(for in-place function only) (for source-to-destiation function only)
- Ptr to array to be sorted in-place - Ptr to array containing source data
- Ptr to auxilary/scratch array - Ptr to array where result will be put
The array return value (pointer to which of the two arrays has
result) is no longer needed because it's implicit in which of the
two functions was called.

As before, records are variable length, where length can be
determined by parsing from the leftmost byte towards the right. For
example, records could be prefixed by their length, or some formal
nesting syntax such as XML or s-expressions could be used for each
record separately. (Obviously prefixing with length would make
sorting much faster, but you take the data the way it's given to
you and must sort in-place or source-to-destination; you don't have
the luxury of re-formatting the data to a more efficient format
before sorting it, otherwise you'd just build a linked list of
records to sort instead of trying to sort records packed in arrays.)

Note that this algorithm is thread safe, whereby sub-tasks can be
parallelized to any degree possible, providing that we have shared
VM with thread-safe paging (or trivially if both arrays fit in
shared physical RAM), and thread-safe CPU access to different
data-allocation units to which all records are aligned. This is
because each recursive call reads and writes *only* within its own
segment of two parallel arrays, which are disjoint with any other
recursive call at any level that might be active at the same time.
(This is "divide and conquer" not just in regard to computations
but also in regard to memory access!)
.

Relevant Pages

  • Re: regex question - trying to find ".mp3" in a SELECT box
    ... But `Array' is a Function object reference. ... Establish a new execution context using F's FormalParameterList, ... Since is not a primitive value, the exception should be thrown. ... | 5.2 Algorithm Conventions ...
    (comp.lang.javascript)
  • Re: Reference to derived type element by index?
    ... as a set of distinctively-named scalars. ... In another scope, the same common block ... would be a single array. ... algorithm and a specific application of the algorithm, ...
    (comp.lang.fortran)
  • Re: counting subsets of S so that sum(S_n) = N
    ... and make my algorithm generate only unique subsets? ... and the array of boolean at one step of the algorithm is ... implementation without needing recursion. ... subsequence in W, process it and return. ...
    (comp.programming)
  • [SUMMARY] Maximum Sub-Array (#131)
    ... # sum the integer values of array contents ... algorithm, ... all possible lengths, to check each subarray. ... $ time ruby -r max_sub_array ...
    (comp.lang.ruby)
  • Re: is there problem that "has to" use recursion
    ... because either way you have defined an algorithm in terms of itself. ... your stack is either the system stack or an array stack. ... Any of the algorithms that optimally use recursion, ...
    (comp.programming)