Basics of algorithms in computer science

# Sorting Algorithms

A sorting algorithm is an algorithm that puts elements of a list in a certain order. Most frequently used orders are numerical order and alphabetical order (often referred to as “lexicographical” order).

There are numerous sorting algorithms such as:

**Insertion Sort** — Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. An insertion sort is less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. A simple example of insertion sort is when people manually sort cards in their hand to they have a clearer picture of how to play their cards. Insertion sorts provide several advantages:

- Simple implementation
- Efficient for very small data sets, can sort a list as it receives it
- Memory efficient

**Selection Sort** — The Selection sort algorithm is based on the idea of finding the minimum or maximum element in an unsorted array and then putting it in its correct position in a sorted array.

**Bubble Sort **— Compare and swapping two elements like small soap bubbles and hence the name given as bubble sort.

**Merge Sort **— Merge Sort divides an input array (numeric or alpha numeric) into two halves and then merges the two sorted halves. A merge() function is used for merging the two halves.

**Quick Sort**- Quick Sort is a type of “divide and conquer algorithm”. It picks an element (numeric or alphanumeric) as a pivot and then partitions the array around the pivot. There are many different methods for a quick sort to pick a pivot

o Pick the first element as pivot.

o Pick the last element as pivot

o Pick a random element as pivot.

o Pick the median as pivot.

**Timsort** — TimSort is a sorting algorithm that is a sort based on Insertion Sort and Merge Sort. Timsort first analyses a list that it is trying to sort and then chooses the best sorting approach based on the analysis of the list. Timsort makes use of Insertion sort and Mergesort