[Algorithm] Types of Sorting

Sorting Algorithms 📚

• 여러 Sorting Algorithm의 원리를 학습하고, 직접 구현해본다.

Name	Best	Average	Worst	Memory	Stable	Method
Quick sort	n log n	n log n	n2	log n	N	Partitioning
Merge sort	n log n	n log n	n log n	n	Y	Merging
Intro sort	n log n	n log n	n log n	log n	N	Partitioning & Selection
Heap sort	n log n	n log n	n log n	1	N	Selection
Insertion sort	n	n2	n2	1	Y	Insertion
Block sort	n	n log n	n log n	1	Y	Insertion & Merging
Tim sort	n	n log n	n log n	n	Y	Insertion & Merging
Cube sort	n	n log n	n log n	n	Y	Insertion
Smooth sort	n	n log n	n log n	1	N	Selection

• 그 중에서도, Worst case가 n log n인 알고리즘은 더욱 깊게 탐구해 볼 계획이다. 해당 알고리즘은 다음과 같다.

Name	Best	Average	Worst	Memory	Stable	Method
Merge sort	n log n	n log n	n log n	n	Y	Merging
Intro sort	n log n	n log n	n log n	log n	N	Partitioning & Selection
Heap sort	n log n	n log n	n log n	1	N	Selection
Block sort	n	n log n	n log n	1	Y	Insertion & Merging
Cube sort	n	n log n	n log n	n	Y	Insertion
Smooth sort	n	n log n	n log n	1	N	Selection

Merge sort

• Wiki:
  • An efficient, general-purpose, and comparison-based sorting algorithm
• Geeks for Geeks:
  • Based on divide and conquer
  • Recursive algorithm
  • Continuously split until it cannot be further divided.
    • it is the base case to stop the recursion
• Divide & Conquer: merge, mergeSort로 나뉜다.
  • 일단 잘 모르겠어서 그대로 한번 써봤다. geeks for geeks 에서 l, i, 1을 다 써놔서 오타 찾느라 한참 걸렸다