# 34.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://2316889115-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FCLYj7ccqvV6l4Pt9R0w5%2Fuploads%2FEBbcRBpJ275clRHizWRe%2Fimage.png?alt=media&#x26;token=03f029c6-677f-4299-bd96-28d8b9c1d954" alt=""><figcaption></figcaption></figure>

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

On the other hand...

<figure><img src="https://2316889115-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FCLYj7ccqvV6l4Pt9R0w5%2Fuploads%2F3v4gy4NRQGaHAXddSsyw%2Fimage.png?alt=media&#x26;token=f7a55be6-6460-440a-b061-0c0da3ab0fda" 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.&#x20;
* 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.&#x20;
* 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?&#x20;

</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://2316889115-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FCLYj7ccqvV6l4Pt9R0w5%2Fuploads%2FaAaScEBnuulum81tD5hq%2Fscreenshot%202023-04-14%20at%201.43.52%20AM.png?alt=media&#x26;token=5705ecb0-ae85-465a-b261-d770a3bba1b8" alt=""><figcaption></figcaption></figure>

<br>
