# 35.1 Sorting Summary

## Other Desirable Sorting Properties: Stability

#### A sort is said to be stable if order of equivalent items is preserved.

<figure><img src="https://github.com/Berkeley-CS61B/fa25-gitbook/blob/main/.gitbook/assets/image%20(85).png" alt=""><figcaption></figcaption></figure>

Equivalent items don’t ‘cross over’ when being stably sorted.

On the other hand...

<figure><img src="https://github.com/Berkeley-CS61B/fa25-gitbook/blob/main/.gitbook/assets/image%20(138).png" alt=""><figcaption></figcaption></figure>

Sorting instability can be really annoying! Wanted students listed alphabetically by section.

\
Arrays.sort()
-------------

In Java, Arrays.sort(someArray) uses:

* Mergesort (specifically the TimSort variant) if someArray consists of Objects.
* Quicksort if someArray consists of primitives.

<figure><img src="https://lh3.googleusercontent.com/PDj3CTwryGwH-zcuR27Eu4VE0vxyJLiRVCAWuaCVrhbO51Cihnnsi6Zb3RGnMNPd0MJdvmAjdeD-8-r_emyVXqkKrxsN6cku7kD2eb_s7sRqpchoO4-FPPP_d2J0XpGF_5NZZHRnnMiJQaGZ_krE_6cOPQ=s2048" alt=""><figcaption></figcaption></figure>

<figure><img src="https://lh4.googleusercontent.com/ouERSw5xhhN_7adslpMp58k5wTeOr8xt2r0ZdeQJnYOD6d43plwpVWaHvyqsCXizBkRrIg6y-CZOCYaVfzbpcAtPsLTU23V4ldc9EbI2sq1Lc9US33BmqpZuVeeZbRyB8WPuLTzSkDsQhSBxY2gpo0c0yg=s2048" alt=""><figcaption></figcaption></figure>

<details>

<summary>Why?</summary>

* Quicksort isn’t stable, but there’s only one way to order them. Wouldn’t have multiple types of orders.
* Could sort by other things, say the sum of the digits.
* Order by the number of digits.
* My usual answer: 5 is just 5. There are no different possible 5's.
* When you are using a primitive value, they are the ‘same’. A 4 is a 4. Unstable sort has no observable effect.
* There’s really only one natural order for numbers, so why not just assume that’s the case and sort them that way.
* By contrast, objects can have many properties, e.g. section and name, so equivalent items CAN be differentiated.
* If you know there’s only one way, can you force Java to use Quicksort?

</details>

## Sorting

Sorting is a foundational problem.

* Obviously useful for putting things in order.
* But can also be used to solve other tasks, sometimes in non-trivial ways.
  * Sorting improves duplicate findings from a naive N^2 to N log N.
  * Sorting improves 3SUM from a naive N^3 to N^2.
* There are many ways to sort an array, each with its own interesting tradeoffs and algorithmic features.

Today we’ll discuss the fundamental nature of the sorting problem itself: How hard is it to sort?

## Sorts Summary

<figure><img src="https://github.com/Berkeley-CS61B/fa25-gitbook/blob/main/.gitbook/assets/screenshot%202023-04-14%20at%201.43.52%20AM.png" alt=""><figcaption></figcaption></figure>

\\
