[prev] 2 [next]

Sorting

Sorting involves arranging a collection of items in order
  • based on some property of the item (e.g. key)
  • using an ordering relation on that property
Sorting occurs in many data contexts, e.g.
  • arrays, linked-lists   (internal, in-memory)
  • files   (external, on-disk)
Different contexts generally require different approaches
  • sorting has been well-studied over the last 40 years
Why is sorting useful?
  • speeds up subsequent searching
  • arranges data in a human-useful way
    (e.g. list of students in a tute class, ordered by family-name or id)
  • provides intermediate step for advanced algorithms
    (e.g. duplicate detection/removal, many DBMS operations)
We initially focus on sorting arrays of Items in ascending order.