Skip to content
Back to Data StructuresAll lessons

Data Structures

Sorted Set

Insert, using an array as shown below: O(n). Sliding items over to make room costs time, even though finding the spot is fast. Contains: O(log n), using binary search on the sorted layout. A real sorted set backed by a balanced tree gets insert down to O(log n) too.

The idea, in plain English

A sorted set is like a bookshelf where, the moment you add a book, you slide it straight into alphabetical position instead of dumping it at the end. The shelf is always in order. If you try to add a book that's already there, nothing changes. It's already shelved.

How it works

  1. 1Keep only unique items, like a normal set. Adding the same item twice changes nothing.
  2. 2But also keep every item in sorted order at all times, not just any order.
  3. 3Insert a new item by finding exactly where it belongs (its sorted position) and sliding it into that spot.
  4. 4Because the layout is always sorted, questions like 'what's the smallest?' or 'what's everything between 20 and 60?' are cheap to answer.

When you'd use it

Use a sorted set for leaderboards that must display scores in order at all times, range questions like 'every score between 50 and 90,' or removing duplicates from data while keeping it sorted for display.

Common beginner mistakes

  • Don't confuse a sorted set with a sorted list that allows duplicates. A sorted set silently drops repeats. A sorted list keeps every copy.
  • Don't assume insert is always instant just because lookups are fast. Keeping items in order costs something. A plain hash set inserts faster but keeps no order at all.

Try it — edit and run

Click the code to edit · press ⌘/Ctrl+↵ to run

Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.

Expected output — hit Run to try it
Sorted: 3 17 42 56 89
Smallest: 3
Largest: 89
Has 56: yes
Has 99: no
Range 20-60: 42 56

Note: This lesson stores items in a plain sorted array, using binary search to find insertion points. That's enough to see the idea. Production sorted sets, like Redis's ZSET, use a skip list or balanced tree underneath, so insert is O(log n) too.

See it in motion

Watch it stay sortedSorted setInsert, using an array as shown below: O(n). Sliding items over to make room costs time, even though finding the spot is fast. Contains: O(log n), using binary search on the sorted layout. A real sorted set backed by a balanced tree gets insert down to O(log n) too.
Incoming numbers
Sorted array (always in order)
empty

Ready. Press play to insert numbers in order.

0
Size
0
Comparisons
0
Shifts
0
Dupes dropped
ComparingJust insertedDuplicate (rejected)Settled

Not sure this is the right topic? See the learning paths → or where this leads →