본 블로그는 개인적인 공부 및 저장의 용도 작성됐습니다.

기본적인 사용법

• sort() 는 arr배열 자체를 바꾸지만 sorted()는 원본 배열을 건드리지 않는다.
• by:를 생략할 경우 default = <

조건 설정

• 이런 식으로 구조체의 값에 따라 설정할 수 있다.
• $0은 앞의 원소, $1은 뒤의 원소가 축약된 것이다.
• sorted 배열은 x의 크기가 작은 순서대로 정렬된다.
• sorted2 배열은 x의 크기가 같으면 y가 큰 순서대로 정렬되고, x의 크기가 다르면 x가 작은 순서대로 정렬된다.

내부 구현

• Swift의 sort는 Timsort로 구현되어있다.
  따라서 O(nlogn)의 시간복잡도를 가지며 안정 정렬이다.

Timsort란 hybrid stable sorting algorithm으로
merge sort와 insertion sort가 섞여있다.

insertion sort도 stable하고 merge sort도 stable하므로 tim sort또한 stable 하다.
하지만 내부 구현이 바뀌어서 stable하지 않게 될 경우에 apple에서 책임지지 않으므로 이것에 의존하여 코드를 구현하면 안된다.

Merge Sort 시간 복잡도

• Best/Worst/Average : O( n log n )

Insert Sort 시간 복잡도

• Best : O(n)

• Worst/Average : O(n^2)

  안정 정렬 / 불안정 정렬

  

  참조
  Timsort
  안정정렬
  공식문서