TIE-20106 1

1 Different Types of Sorting Algorithms

This chapter discusses sorting algorithms that use other
approaches than comparisons to determine the order of the
elements.
The maximum efficiency of comparison sorts, i.e. sorting based
on the comparisons of the elements, is aldo examined.
Finally, the chapter covers the factors for choosing an
algorithm.
TIE-20106 2

1.1 Other Sorting Algorithms

All sorting algorithms covered so far have been based on
comparisons.
• They determine the correct order of elements based on
comparing their values to eachother.

It is possible to use other information besides comparisons to

sort data.
TIE-20106 3

Sorting by counting
Let’s assume that the value range of the keys is small, atmost
the same range than the amount of the elements.
• For simplicity we assume that the keys of the elements are
from the set {1, 2, . . . , k}, and k = O(n).
• The amount of elements with each given key is calculated.
• Based on the result the elements are placed directly into
their correct positions.
TIE-20106 4

C OUNTING -S ORT(A, B, k)
1 for i := 1 to k do
2 C[i] := 0 (initialize a temp array C with zero)
3 for j := 1 to A.length do
4 C[A[j].key] := C[A[j].key] + 1 (calculate the amount of elements with key = i)
5 for i := 2 to k do
6 C[i] := C[i] + C[i − 1] (calculate how many keys ≤ i)
7 for j := A.length downto 1 do (scan the array from end to beginning)
8 B[C[A[j].key]] := A[j] (place the element into the output array)
9 C[A[j].key] := C[A[j].key] − 1 (the next correct location is a step to the left)

The algorithm places the elements to their correct location in

reverse order to quarantee stability.
TIE-20106 5

Running-time:
• The first and the third for-loop take Θ(k) time.
• The second and the last for-loop take Θ(n) time.
⇒ The running time is Θ(n + k).
• If k = O(n), the running-time is Θ(n).
• All basic operations are simple and there are only a few of
them in each loop so the constant coefficient is also small.

C OUNTING -S ORT is not worth using if k  n.

• The memory consumption of the algorithm is Θ(k).
• Usually k  n.
– for example: all possible social security numbers  the
social security numbers of TUT personnel
TIE-20106 6

Sometimes there is a need to be able to sort based on seeral

keys or a key with several parts.
• the list of exam results: sort first based on the department
and then those into an alphabetical order
• dates: first based on the year, then the month, and the day
• a deck of cards: first based on the suit and then those
according to the numbers

The different criteria are taken into account as follows

• The most significant criterion according to which the values
of the elements differ determines the result of the
comparison.
• If the elements are equal with each criteria they are
considered equal.
TIE-20106 7

The problem can be solved with a comparison sort (e.g. by

using a suitable comparison operator in Q UICKSORT or
M ERGESORT). Example: comparing dates:
DATE -C OMPARE(x, y)
1 if x.year < y.year then return “smaller”
2 if x.year > y.year then return “greater”
3 if x.month < y.month then return “smaller”
4 if x.month > y.month then return “greater”
5 if x.day < y.day then return “smaller”
6 if x.day > y.day then return “greater”
7 return “equal”

Sometimes it makes sense to handle the input one criterion at

a time.
• For example it’s easiest to sort a deck of cards into four piles
based on the suits and then each suit separately.
TIE-20106 8

The range of values in the significant criteria is often small

when compared to the amount of elements and thus
C OUNTING -S ORT can be used.
There are two different algorithms available for sorting with
multiple keys.
• LSD-R ADIX -S ORT
– the array is sorted first according to the least significant
digit, then the second least significant etc.
– the sorting algorithm needs to be stable - otherwise the
array would be sorted only according to the most
significant criterion
– C OUNTING -S ORT is a suitable algorithm
– comparison algorithms are not worth using since they
would sort the array with approximately the same
amount of effort directly at one go

LSD-R ADIX -S ORT(A, d)

1 for i := 1 to d do (run through the criteria, least significant first)
2 . sort A with a stable sort according to criterion i
TIE-20106 9

• MSD-R ADIX -S ORT

– the array is first sorted according to the most significant
digit and then the subarrays with equal keys according to
the next significant digit etc.
– does not require the sorting algorithm to be stable
– usable when sorting character strings of different lengths
– checks only as many of the sorting criterions as is needed
to determine the order
– more complex to implement than LSD-R ADIX -S ORT
⇒ the algorithm is not given here
TIE-20106 10

The efficiency of R ADIX -S ORT when using C OUNTING -S ORT:

• sorting according to one criterion: Θ(n + k)
• amount of different criteria is d
⇒ total efficiency Θ(dn + dk)
• k is usually constant
⇒ total efficiency Θ(dn), or Θ(n), if d is also constant

R ADIX -S ORT appears to be a O(n) sorting algorithm with certain

assumptions.
Is is better than the comparison sorts in general?
TIE-20106 11

When analyzing the efficiency of sorting algorithms it makes

sense to assume that all (or most) of the elements have
different values.
• For example I NSERTION -S ORT is O(n), if all elements are equal.
• If the elements are all different and the size of value range
of one criterion is constant k, k d ≥ n ⇒ d ≥ logk n = Θ(lg n)
⇒ R ADIX -S ORT is Θ(dn) = Θ(n lg n), if we assume that the
element values are mostly different from each other.
R ADIX -S ORT is asymptotically as slow as other good sorting
algorithms.
• By assuming a constant d, R ADIX -S ORT is Θ(n), but then with
large values of n most elements are equal to eachother.
TIE-20106 12

Advantages and disadvantages of R ADIX -S ORT

Advantages:
• R ADIX -S ORT is able to compete in efficiency with Q UICKSORT
for example
– if the keys are 32-bit numbers and the array is sorted
according to 8 bits at a time
⇒ k = 28 and d = 4
⇒ C OUNTING -S ORT is called four times
• R ADIX -S ORT is well suited for sorting according to keys with
multiple parts when the parts of the key have a small value
range.
– e.g. sorting a text file according to the characters on the
given columns (cmp. Unix or MS/DOS sort)
Disadvantages:
• C OUNTING -S ORT requires another array B of n elements
where it builds the result and a temp array of k elements.
⇒ It requires Θ(n) extra memory which is significantly larger
than for example with Q UICKSORT and H EAPSORT.
TIE-20106 13

Bucket sort
Let’s assume that the keys are within a known range of values
and the key values are evenly distributed.
• Each key is just as probable.
• For the sake of an example we’ll assume that the key values
are between zero and one.
• Let’s use n buckets B[0] . . . B[n − 1].
B UCKET-S ORT(A)
1 n := A.length
2 for i := 1 to n do (go through the elements)
3 I NSERT(B[bn · A[i]c], A[i]) (throw the element into the correct bucket)
4 k := 1 (start filling the array from index 1)
5 for i := 0 to n − 1 do (go through the buckets)
6 while B[i] not empty do (empty non-empty buckets...)
7 A[k] := E XTRACT-M IN(B[i]) (... by moving the elements, smallest first...)
8 k := k + 1 (... into the correct location in the result array)
TIE-20106 14

Implementation of the buckets:

• Operations I NSERT and E XTRACT-M IN are needed.
⇒ The bucket is actually a priority queue.
• The size of the buckets varies a lot.
– usually the amount of elements in the bucket is ≈ 1
– however it is possible that every element end up in the
same bucket
⇒ an implementation that uses a heap would require Θ(n)
for each bucket,s Θ(n2) in total
• On the other hand, the implementation does not need to
be very efficient for large buckets since they are rare. ⇒ In
practise the buckets should be implemented as lists.
– I NSERT links the incoming element to its correct location in
the list, Θ(list length) time is used
– E XTRACT-M IN removes and returns the first element in the
list, Θ(1) time is used
TIE-20106 15

the average efficiency of B UCKET-S ORT:

• We assumed the keys are evenly distributed.
⇒ On average one element falls into each bucket and very
rarely a significantly larger amount of elements fall into the
same bucket.
• The first for-loop runs through all of the elements, Θ(n).
• The second for-loop runs through the buckets, Θ(n).
• The while-loop runs through all of the elements in all of its
iterations in total once, Θ(n).
• I NSERT is on average constant time, since there is on
average one element in the bucket.
• E XTRACT-M IN is constant time.
⇒ The total running-time is Θ(n) on average.
In the slowest case all elements fall into the same bucket in an
ascending order.
• I NSERT takes a linear amount of time
⇒ The total running-time is Θ(n2) in the worst-case.
TIE-20106 16

1.2 How fast can we sort?

Sorting an array actually creates the per-
31 41 59 26 58 41
mutation of its elements where the origi-
nal array is completely sorted.
• If the elements are all different, the 26 31 41 41 58 59
permutation is unique. ⇒ Sorting
searches for that permutation from the
set of all possible permutations.

For example the functionality of I NSERTION -S ORT, M ERGE -S ORT,

H EAPSORT and Q UICKSORT is based on comparisons between
the elements.
• Information about the correct permutation is collected only
by comparing the elements together.
What would be the smallest amount of comparisons that is
enough to find the correct permutation for sure?
TIE-20106 17

• An array of n elements of different values has 1 · 2 · 3 · . . . · n

i.e. n! permutations.
• The amount of comparisons needed must find the only
correct alternative.
• Each comparison A[i] ≤ A[j] (or A[i] < A[j]) divides the
permutations into two groups: those where the order of A[i]
and A[j] must be switched and those where the order is
correct so...
– one comparison in enough to pick the right alternative
from atmost two
– two comparisons in enough to pick the right one from
atmost four
– ...
– k comparisons in enough to pick the right alternative from
atmost 2k
⇒ choosing the right one from x alternatives requires at
least dlg xe comparisons
TIE-20106 18

• If the size of the array is n, there are n! permutations

⇒ At least dlg n!e comparisons is required
⇒ a comparison sort algorithm needs to use Ω(dlg n!e) time.
How large is dlg n!e ?
• dlg n!e ≥ lg n! = Pnk=1 lg k ≥ Pnk=d n2 e lg n2 ≥ n2 · lg n2 = 12 n lg n − 12 n =
Ω(n lg n) − Ω(n) = Ω(n lg n)
• on the other hand dlg n!e < n lg n + 1 = O(n lg n)
⇒ dlg n!e = Θ(n lg n)
TIE-20106 19

Every comparison sort algorithm needs to use Ω(n lg n) time in

the slowest case.
• On the other hand H EAPSORT and M ERGE -S ORT are O(n lg n)
in the slowest case.
⇒ In the slowest case sorting based on comparisons
between elements is possible in Θ(n lg n) time, but no faster.
• H EAPSORT and M ERGE -S ORT have an optimal asymptotic
running-time in the slowest case.
• Sorting is truly asymptotically more time consuming than
finding the median value, which can be done in the slowest
possible case in O(n).
TIE-20106 20

1.3 Choosing an algorithm

The key factor in choosing an algorithm is usually its efficiency
in that situation. However, there are other factors:
• implementation is easy
– is there a suitable algorithm already available?
– is the advantage of improved efficiency worth the effort
of implementing a more complex algorithm?
– simpler code may not contain errors as easily
– a simpler solution is easier to maintain
• precision of the results
– with real numbers round-off errors can be a significant
problem
• variation in the running-time
– e.g. in signal processing the running-time must not vary at
all
TIE-20106 21

The programming environment also sets its limitations:

• many languages require that a maximum size is defined for
arrays
⇒ algorithms using arrays get a compile time, artificial
upper limit
– with list structures and dynamic arrays the algorithm works
as long as there is memory available in the computer
• the memory can suddenly run out with lists, but not with
arrays of a fixed size
⇒ list structures are not always suitable for embedded
systems
• in some computers the space reserved for recursion is much
smaller than the space for the rest of the data
⇒ if a lot of memory is needed, a non-recursive algorithm
(or implementation) must be chosen
TIE-20106 22

If the efficiency is the primary factor in the selection, at least

the following should be taken into account:
• Is the size of the input data so large that the asymptotic
efficiency gives the right idea about the overall efficiency?
• Can the worst-case be slow if the efficiency is good in the
average case?
• Is memory use a factor?
• Is there a certain regularity in the input that can be
advantageous?
– with one execution?
– with several executions?
• Is there a certain regularity in the input that often is the
worst-case for some algorithm?
TIE-20106 23

Example: contacts
• operations
– finding a phonenumber based on the
name
– adding a new contact into the phone-
book
– removing a contact and all the related
information
• assumptions
– additions and removals are needed
rarely
– phonenumber queries are done often
– additions and removals are done in
groups
TIE-20106 24

1st attempt: unsorted array

Virtanen Järvinen Lahtinen

123 555 123 111 123 444
1 2 n
• Adding a new name to the end: O(1).
• Searching by scanning the elements from the beginnning
(or end): O(n).
• Removing by moving the last element to the place of the
removed element: O(1) + search costs = O(n).
⇒ The solution is not suitable since the operations that are
needed often are slow.
TIE-20106 25

2nd attempt: sorted array, 1st version

• Adding the new names directly to their correct location in
the alphabetical order. The rest of the elements are moved
one step forwards: O(n).
• Removing by moving the elements one step backwards:
O(n).
• Searching with B IN -S EARCH: Θ(lg n).
⇒ The search is efficient but the removal and addition are still
slow.
• The solution seems better than the first attempt if our original
assumption is correct and searches are done more
frequently than additions and removals.
TIE-20106 26

3rd attempt: an almost sorted array

• Keep most of the array sorted and a small unsorted
segment at the end of the array (size O(1)).
• Additions are done to the segment at the end: O(1).
• Search is done first with binary search in the sorted part and
then if needed by scanning the unsorted part at the end:
O(lg n) + O(l).
• Removal is done by leaving the name in and changing the
number to 0: O(1) + search costs = O(lg n) + O(l).
• When the unsorted end segment has become too large,
sort the entire array: Θ(n lg n).
• A mediocre solution, but
– Θ(l) can be large
– sorting every now and then costs time
TIE-20106 27

4th attempt: a sorted array, 2nd. version

• Let’s use the information that additions and removal are
done in groups to our advantage.
• Sort the groups of additions and removals.
• Merge the array and the group of additions (like with
M ERGE) by removing the elements in the group of removals
simultaneously.
• Now the search is still logarithmic.
• Addition and removal uses O(l lg l) + O(p lg p) + O(n), when l
is the amount of additions and p is the amount of removals
• Pretty good!

The problem could also be solved with dynamic sets covered

later on the course and naturally, with programming
languages’ library implementations such as the C++
containers.