c# 정렬, 상황 별 활용

1. C#에서의 Array.Sort()

---

• C#에서의 Array.Sort()는 Intro 정렬이다.
  -> 삽입 + 퀵 + 힙

---

2. 정렬별 사용 상황

---

• 삽입과 선택정렬은 연결리스트에서는 구현이 어렵기 때문에, 버블정렬로 정렬.
  -> 배열은 임의접근이 가능하지만, 연결리스트는 전체를 순회해서 바꿔야할 노드를 찾아야함.
• 평균적으로 퀵정렬이 제일 빠름, but 최악의 경우 퀵정렬은 O(n^2).
  -> 퀵 > 머지 > 힙.
• 최악으로 세타(nlogn)이 걸리고, in-place인 경우, 힙 사용!
  -> 머지는 세타(n)만큼 extraspace를 사용하기때문에, 힙은 재귀가아닌 포문형식을 사용해서 in-place
• 머지는 stable, 퀵과 힙은 unstable정렬.
  -> 똑같은 데이터를 순서대로 정렬할때는 머지정렬을 이용하는것이 좋다