:PROPERTIES: :ID: 9c2f8198-fead-4602-aa99-8f5312e239fb :mtime: 20231016020653 :ctime: 20231016020632 :END: #+title: Sorting a List #+filetags: :public:project: * Definition Sorting a list is a type of problem where the input is a list, and the output is that sorted list. * Reasons to Sort a List There are many reasons why it is useful to sort a list. These include: - Making search easier - finding duplicates. * Types of Sorting Algorithms Here is a list of algorithms for sorting - [[id:13b99e2c-1873-48f9-906b-f4e5f2015a0e][insertion sort]] - [[id:f37ce2ed-27c4-4208-8995-e45e6ae49801][quicksort]] - [[id:6409e8d1-5a47-4c95-99f3-c1a8a02ecc3f][mergesort]] * [[id:43dd8110-2e8e-42a3-8d7a-55da895da68a][Asymptotic Complexity]] of sorting a list ** Comparison Sort Imagine you have a comparison function $C(x,y)$. We judge the efficiency of the sort by how many comparisons you need to sort a list. All comparison sorts are $O(n \log n)$.