Re: Insert Into a Sorted Array

The mergesort version of sort in perl 5.8+ will do that as well as anything¹ by just sorting in the new value,

@known = sort byIndex @known;
@known = sort byIndex $newValue, @known;
[download]

The quicksort of previous versions of perl is bad for this. It has a quadratic worst case for nearly sorted lists.

¹ Actually not as good as a binary search for a single insertion point, which is O(logN). That is how you'd perform your own suggestion. As tachyon says, though, insertion with splice is still O(N/2).

After Compline,
Zaxo

Comment on Re: Insert Into a Sorted Array Download Code

Replies are listed 'Best First'.
Re^2: Insert Into a Sorted Array by ketema (Scribe) on Sep 29, 2004 at 03:30 UTC
This I would like for ease of readability, did a perldoc -f mergesort, and didn't find anything. Where is this function documented?	[reply]
Re^3: Insert Into a Sorted Array by Zaxo (Archbishop) on Sep 29, 2004 at 03:44 UTC
The `perldoc sort` (no -f!) pod documents the sort.pm pragma. It explains selecting the kind of function which performs sort in perl 5.8. After Compline, Zaxo	[reply]