0000033: Re: Broken Sort Code in StdLib

View Issue Details [ Jump to Notes ]

[ Issue History ] [ Print ]

Project

Category

View Status

Date Submitted

Last Update

0000033

OCaml

OCaml general

public

2000-01-27 18:46

2000-04-17 13:45

Reporter

administrator

Assigned To

Priority

normal

Severity

minor

Reproducibility

always

Status

closed

Resolution

fixed

Platform

OS Version

Product Version

Target Version

Fixed in Version

Summary

0000033: Re: Broken Sort Code in StdLib

Description

Hi,

Thank you for your message to the Caml mailing list.

However your message seems to be a bug report; hence I send it to the
relevant mailing list

caml-bugs@inria.fr

Thank again for your interest in Caml.

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://cristal.inria.fr/~weis/ [^]

> Dear Caml Crowd...
>
> There still appears to be a problem with the Standard Library Sort.array
> routine. Violation of boundary conditions occur on some occaisions that
> manifest an invalid page fault runtime error.
>
> I have copied the code from the source, modified to explicitly check for
> boundary violations and this appears to fix the problem. My fix is probably
> non-optimal.
>
> The original code fragment is
>
> ...
> let pivot = unsafe_get arr mid in
> let i = ref (lo + 1) and j = ref (hi - 1) in
> while !i < !j do
> while not (cmp pivot (unsafe_get arr !i)) do incr i done;
> while not (cmp (unsafe_get arr !j) pivot) do decr j done;
> if !i < !j then swap arr !i !j;
> incr i; decr j
> done;
> ...
>
> The modified code fragment is:
> (Note the explicit checks in the innermost while loops.)
>
> let pivot = unsafe_get arr hi in
> let i = ref lo and j = ref hi in
> while !i < !j do
> while !i < hi && order (unsafe_get arr !i) pivot do incr i done;
> while !j > lo && order pivot (unsafe_get arr !j) do decr j done;
> if !i < !j then swap arr !i !j
> done;
>
> This problem was first noticed in OCaml 2.03 and has been verified to exist
> in OCaml 2.99.
>
> David McClain, Sr. Scientist
> Raytheon Systems Co.
> Tucson, AZ

Issue History
Date Modified	Username	Field	Change
2005-11-18 10:13	administrator	New Issue

Notes
(0000305) administrator (administrator) 2000-04-17 13:45	Fixed in 3.00 (Sort.array checks for reflexive ordering relation; code superceded by Array.sort)

Relationships