ttwpa

Temp Vars

Why Swapping Two Things Needs a Third Slot

Try this in a spreadsheet. Cell B3 says "Chicago" and cell B5 says "Denver", and they need to trade places. There is no way to do it directly. Copy B3, paste it into B5, and Denver is gone. Copy B5 first, and the same thing happens in the other direction.

So you do this instead:

  1. Copy B3 into some empty cell off to the side, say F1.
  2. Copy B5 into B3.
  3. Copy F1 into B5.
  4. Clear F1.

The same constraint we see with F1's necessary existence shows up outside spreadsheets. Two files that need to trade names cannot do it directly, because renaming the first onto the second deletes the second. You rename one to a temporary name first. Same problem, same fix.

In code this is a temp variable

temp = a
a = b
b = temp

temp is cell F1. Without it, a = b destroys the value in a before line two can use it, which is exactly the failed spreadsheet attempt.

This is called a swap, and it is the operation that sorting algorithms are built out of.

Sorting is comparisons plus swaps

Every comparison sort does the same two things: look at two items and decide which should come first, then move items into place. The algorithms differ only in which pairs they look at and in what order. Understanding that is most of understanding sorting.

The costs worth tracking are how many comparisons an algorithm does and how many writes it does, and those two numbers do not move together.

Bubble sort

Compare the first item to the second and swap them if they are out of order. Then compare the second to the third. Keep going to the end, then start over from the beginning, and stop when a full pass produces no swaps.

It works because a swap only ever fixes a local problem, and repeating enough passes eventually fixes all of them. It requires no memory of anything except the two items currently in front of you.

That is also its problem. It does roughly n²/2 comparisons and up to n²/2 swaps, which is the worst of both. Sorting 1,000 items means around half a million of each. It survives in classrooms because it is easy to explain and easy to prove correct, and almost nowhere else.

Selection sort

Scan the entire unsorted portion, find the item that belongs next, and swap it into position. Then scan again for the one after that.

It still does about n²/2 comparisons, since you rescan the remaining items every round. But it does exactly n-1 swaps for the whole sort, one per position, and never more.

That tradeoff is the reason it exists. When reading is cheap and writing is expensive, selection sort is genuinely the right choice. Flash memory and EEPROM wear out after a limited number of writes. Rearranging physical objects costs real effort no matter how long you spent deciding. If moving is what hurts, an algorithm that thinks a lot and moves once per slot wins.

Insertion sort

Take the next unsorted item and move it backward past every item larger than it until it lands in the right place. Then take the next one.

This is how most people sort a hand of playing cards, and it has two properties the others do not.

First, it is fast when the data is already close to sorted. Each item only travels as far as it is out of place, so a nearly-ordered list costs close to n operations instead of n². Real data is often nearly ordered, which is why this matters more than it sounds.

Second, it works on data arriving one piece at a time. You never need the whole list up front, because every item gets placed into an already-sorted prefix. Bubble sort and selection sort both need the full list before they can start.

Its weakness is the same as the others. On randomly ordered data it does about n²/4 comparisons and moves, so it does not scale.

What actually gets used

Merge sort splits the list in half, sorts each half, then walks the two sorted halves and merges them into order. It runs in n log n time no matter what the input looks like, but it needs a second array to merge into.

Quicksort picks a pivot value and swaps items around until everything smaller is on the left and everything larger is on the right, then repeats on each side. It needs no extra array, and it is usually the fastest option in practice, though a bad pivot choice degrades it to n².

Neither of these is what your language actually calls. Python and Java use Timsort, which looks for runs that are already in order and merges them. C++ uses introsort, which runs quicksort and bails out to heapsort if the recursion gets too deep. Both of them fall back to insertion sort once a chunk gets small enough, usually under about sixteen elements, because on tiny inputs its low overhead beats the smarter algorithms.

The moving usually costs more than the deciding

Comparing two items is one operation. Moving one is not.

Deleting an element from the middle of an array requires shifting every element after it one position left. Inserting requires shifting them right. There is no way around it, because array positions are fixed and contiguous, which is the same fact that made the swap need a third slot in the first place.

Your spreadsheet and your text editor do this shifting for you, fast enough that you never notice. In code you either do it yourself or pick a structure that does not need it. A linked list can insert and delete in the middle without shifting anything, because its positions are not fixed. It pays for that by being unable to jump directly to element 500.

Swapping without a temp variable

You can swap two integers with no third slot at all:

a = a ^ b
b = a ^ b
a = a ^ b

XOR (^) compares two values bit by bit and produces a 1 wherever the bits differ and a 0 wherever they match. The property that makes this work is that XOR undoes itself: x ^ y ^ y gives back x. Applying the same value twice cancels out.

That means a ^ b is a reversible mixture of both numbers rather than a destructive overwrite. Nothing is lost by storing it, because either original can be pulled back out by XORing the mixture with the other one.

Walking through it with a starting as A and b starting as B:

  1. a = a ^ b puts the mixture A ^ B into a. B is still sitting in b.
  2. b = a ^ b computes (A ^ B) ^ B, the Bs cancel, and b becomes A.
  3. a = a ^ b computes (A ^ B) ^ A, the As cancel, and a becomes B.

The holding place did not disappear. It is hidden inside a, which spends two of the three steps holding both values at once.

There are two reasons this stays in interview questions instead of real code. First, it breaks when a and b are the same location, which happens easily inside a sort when both indices land on the same element. Step 1 becomes x = x ^ x, which is 0, and the value is destroyed before step 2 can recover it. Second, it is slower. The three lines depend on each other in sequence so the processor cannot overlap them, while a plain three-line swap usually compiles down to register moves or a single exchange instruction and costs nothing. The arithmetic version (a = a + b; b = a - b; a = a - b) has the same problems plus overflow, and XOR only works on integers and pointers, so it is useless for floats, structs, or strings.

Optimizations that reduce the shuffling

Since removing the holding place buys nothing, the useful optimizations go the other way. They keep it and cut down the number of trips.

Shift instead of swapping repeatedly. A naive insertion sort swaps an item with each neighbor in turn. Each swap is three assignments, so moving an item back five positions costs fifteen. The standard implementation lifts the item into temp once, shifts each larger element one slot over at one assignment each, then drops the item into the gap. Same result, seven assignments instead of fifteen.

temp = arr[i]
while j >= 0 and arr[j] > temp:
    arr[j+1] = arr[j]
    j -= 1
arr[j+1] = temp

Follow the cycle instead of swapping pairs. If you already know where everything belongs, pairwise swaps repeat work. Three items rotating positions takes two swaps, which is six writes. Following the cycle takes four: park the first item, move the one that belongs in its place directly there, move the next one directly into the gap that opens, then drop the parked item into the last opening. One holding place for the entire chain and every item written exactly once, which is the theoretical minimum. This is cycle sort, and it matters wherever writes are expensive.

Rotate with reversals instead of a buffer. Moving a block of items from one position to another is a rotation of everything between the source and the destination. You can do it with no scratch space by reversing the first block, reversing the second, then reversing the whole span. Each element gets written twice and nothing leaves the array. This is what std::rotate does.

Swap references, not contents. The cheapest swap moves nothing. Exchanging two std::vector objects in C++ swaps three pointers and finishes in constant time regardless of how much data they hold. Sorting large records is usually done by sorting an array of pointers or indices and leaving the records where they are.

Merge sort makes the opposite trade, allocating a full second array and accepting the memory cost for a simpler merge. The real question is rarely whether to use scratch space, only how much and how often to return to it.

Where this comes up

Almost nobody implements a sort. The standard library version is faster and already handles every case.

The swap itself comes up constantly, usually disguised as something else.

Drag-and-drop reordering is the common one. Say each row in a table has an integer position column with a unique constraint on it, and the user drags row 5 up to position 2. You cannot do it in one UPDATE. The moment row 5 claims position 2, two rows hold that value and the constraint rejects the write. The usual fix is to move the dragged row to a value that cannot collide, often -1 or a number past the end of the list, shift the rows between the old and new positions, then write the real value in. The out-of-range position is cell F1.

Reversing an array in place is a loop of swaps between the two ends, each one needing its own temp. Fisher-Yates shuffling walks backward through an array swapping each element with a randomly chosen earlier one, same thing on every iteration. Both are cases where you cannot sidestep the problem by inserting and deleting, because the slots are fixed.

Two other things fall out of this. If a collection spends most of its life having items inserted and removed from the middle, the cost is the shifting rather than anything else, and an array is the wrong container. And if items arrive one at a time and the list stays close to ordered, insertion sort is a reasonable production choice rather than only a teaching example, which is why the standard libraries fall back to it.