Knuth Heapsort

Matlab implementation of Knuth's heapsort.

Use this Matlab heapsort when you want to compare results from heapsorts in other languages/platforms (fortran, C, SciPy, etc.). Matlab's sort preserves the order of matching entries in a list and is thus a "stable" sort. Heapsort is "unstable" in that it does not preserve the order for matching entries (see example below), thus giving different results from Matlab's sort.

This can be useful, for example, when comparing results during a porting of legacy code into matlab.

% [r,TAGS]=tagged_real_heapsort(r,TAGS);
%
% WRITTEN BY BILL LEDSHAM 4/3/80
%
% HEAPSORT FROM ALGORITHM H IN KNUTH VOL. 3 PP 146-147
%
% VARIABLE USAGE:
% r -> INPUT/OUTPUT OF KEYS TO BE SORTED.
% TAGS -> INPUT OUTPUT OF TAGS THAT WILL FOLLOW r IN SORT ORDER
% n -> NUMBER OF KEYS
%
%
% EXAMPLE:
% r=[4,5,1,5,8,5,9,5];
% t=1:8;
% [r,t]=tagged_real_heapsort(r,t)
% r =
% 1 4 5 5 5 5 8 9
% t =
% 3 1 6 2 4 8 5 7
%
% Converted into Matlab by Ben Barrowes 8/07 in part using f2matlab
% (origninal fortran at end of file)