์ปดํจํฐ๊ณผํ์์, ๋ณํฉ ์ ๋ ฌ(์ผ๋ฐ์ ์ผ๋ก mergesort๋ผ๊ณ ์ฐ๋)์ ํจ์จ์ ์ด๊ณ , ๋ฒ์ฉ์ ์ธ, ๋น๊ต ๊ธฐ๋ฐ์ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ ๋๋ค. ๋๋ถ๋ถ์ ๊ตฌํ๋ค์ ์์ ์ ์ธ ์ ๋ ฌ์ ๋ง๋ค์ด๋ด๋ฉฐ, ์ด๋ ์ ๋ ฌ๋ ์ฐ์ถ๋ฌผ์์ ๋์ผํ ์์๋ค์ ์ ๋ ฅ ์์๊ฐ ์ ์ง๋๋ค๋ ๊ฒ์ ์๋ฏธํฉ๋๋ค. ๋ณํฉ ์ ๋ ฌ์ 1945๋ ์ John von Neumann์ด ๋ง๋ ๋ถํ ์ ๋ณต ์๊ณ ๋ฆฌ์ฆ์ ๋๋ค.
๋ณํฉ ์ ๋ ฌ์ ์์์ ๋๋ค. ์ฐ์ ๋ฆฌ์คํธ๋ฅผ ๊ฐ์ฅ ์์ ๋จ์๋ก ๋๋๊ณ (ํ ๊ฐ์ ์์), ๋ ๊ฐ์ ์ธ์ ํ ๋ฆฌ์คํธ๋ฅผ ์ ๋ ฌํ๊ณ ๋ณํฉํ๊ธฐ ์ํด ๊ฐ ์์์ ์ธ์ ํ ๋ฆฌ์คํธ๋ฅผ ๋น๊ตํฉ๋๋ค. ๋ง์ง๋ง์ผ๋ก ๋ชจ๋ ์์๋ค์ ์ ๋ ฌ๋๊ณ ๋ณํฉ๋ฉ๋๋ค.
์ฌ๊ท์ ์ธ ๋ณํฉ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ 7๊ฐ์ ์ ์๊ฐ์ ๊ฐ์ง ๋ฐฐ์ด์ ์ ๋ ฌํ๋๋ฐ ์ฌ์ฉ๋ฉ๋๋ค. ๋ค์์ ํฉ๋ณ ์ ๋ ฌ์ ๋ชจ๋ฐฉํ๊ธฐ ์ํด ์ฌ๋์ด ์ทจํ๋ ๋จ๊ณ์ ๋๋ค.(ํํฅ์)
Name | Best | Average | Worst | Memory | Stable | Comments |
---|---|---|---|---|---|---|
Merge sort | nย log(n) | nย log(n) | nย log(n) | n | Yes |