# algorithm-sorting-and-searching

## Sorting And Searching

### Group Anagrams

Write a method to sort an array ot strings so that all tne anagrnms are next to each other.

anagrams are words that have the 相同的字符 but in 不同的顺序.

This algorithm will take `O(n log(n))` time.

### Sort Big File

Imagine you have a 20 GB file with one string per line. Explain how you would sort the file.

We’ll divide the file into chunks, which are x megabytes each, where x is the amount of memory we have available. Each chunk is sorted separately and then saved back to the file system.

Once all the chunks are sorted, we merge the chunks, one by one. At the end, we have a fully sorted file. This algorithm is known as external sort.

### Missing Int

Given an input file with four billion non-negative integers, provide an algorithm to generate an integer that is not contained in the file. Assume you have 1 GB of memory available for this task.

What if you have only 10 MB of memory? Assume that all the values are distinct and we now have no more than one billion non-negative integers.

• 使用 `BitVector`

### JDK 1.8 - `Arrays.sort`

• 当元素数量小于 `47` 个的时候,使用 `InsertionSort`
• 当元素数量小于 `286` 个的时候,使用 `DualPivotQuickSort`

### 查找重复数字

• `4KB` = `4 * 2^10 * 8``bit` 位 > `32000`
• `new BitSet(32000)`

## 推荐文章 