Ola Petersson

TCS Journal 1996 Journal Article

Exploiting few inversions when sorting: Sequential and parallel algorithms

• Christos Levcopoulos
• Ola Petersson

We consider the problem of taking advantage of existing order within the input sequence when sorting. The measure of presortedness used is the number of inversions. Let X be a sequence of length n and let Inv(X) be the (unknown) number of inversions in X. Our main results are: • • X can be sorted in-place, i. e. using only O(log n) bits of extra space, in time O(n log( Inv(X) n )), which is optimal with respect to the number of inversions. • • Given p processors on an EREW PRAM, X can be sorted in time O( n log( Inv(X) n ) p + log n), which is optimal with respect to the number of inversions.

STOC Conference 1995 Conference Paper

A tight lower bound for searching a sorted array

• Arne Andersson
• Johan Håstad
• Ola Petersson

SODA Conference 1995 Conference Paper

On-line Approximate List Indexing with Applications

• Arne Andersson
• Ola Petersson

STOC Conference 1994 Conference Paper

The complexity of searching a sorted array of strings

• Arne Andersson
• Torben Hagerup
• Johan Håstad
• Ola Petersson

MFCS Conference 1992 Conference Paper

Merging and Sorting Strings in Parallel

• Torben Hagerup
• Ola Petersson

Abstract We show that strings of characters, equipped with the usual lexicographical ordering, can be merged and sorted in parallel as efficiently as integers, although with some loss in speed. Specifically, our main results are: Two sorted lists of strings, containing altogether n characters, can be merged with an optimal time-processor product of O(n) in O (log n ) time on a CRCW PRAM, and in O ((log n ) 2 ) time on an EREW PRAM. Suppose that n integers of size polynomial in n can be sorted in time O(t(n) ) with a time-processor product of O(nf(n)) on a CRCW PRAM, a CREW PRAM or an EREW PRAM, for nondecreasing functions t, f: ℕ → ℕ. Then a list of strings, containing altogether n characters drawn from an alphabet of size polynomial in n, can be sorted in time O(t(n) log n) with a time-processor product of O(n f(n) + n log log n ) on a PRAM of the same type. In particular, such a list can be sorted in O((log n) 2 /log log n ) time with a time-processor product of O ( n log log n ) on a CRCW PRAM.

MFCS Conference 1990 Conference Paper

Splitsort - An Adaptive Sorting Algorithm

• Christos Levcopoulos
• Ola Petersson

Abstract We present a new sorting algorithm, called Splitsort which adapts to existing order within the input sequence. The algorithm is optimal with respect to several known measures of presortedness, including the number of inversions, for which no such simple and space efficient algorithm was known before. The amount of extra space needed is only n + O (log n ) pointers. Splitsort uses a simple data structure and is easy to code. In the worst case Splitsort performs 2. 5 n log 2 n comparisons, but if the input is presorted according to some of the measures it completes the sorting task considerably faster. We also show how a variant of the algorithm can be implemented to run in-place.