Sorting 

Let A be the list of n elements A1, A2, … An in memory. Sorting A refer to the operating of rearranging the contents of A so that there are increasing in order that is so that
A1<=A2<=A3<=…An
Sorting algorithm is an algorithm that puts elements of a list in a certain order. The mostused orders are numerical order and lexicographical order. Efficient sorting is important to optimizing the use of other algorithms (such as search and merge algorithms) that require sorted lists to work correctly; it is also often useful for canonicalizing data and for producing humanreadable output.
Selection Sort:
This type of sorting is called "Selection Sort" because it works by repeatedly element. It works as follows: first find the smallest in the array and exchange it with the element in the first position, then find the second smallest element and exchange it with the element in the second position, and continue in this way until the entire array is sorted.
Insertion Sort:
Insertion sort keeps making the left side of the array sorted until the whole array is sorted. It sorts the values seen so far and repeatedly inserts unseen values in the array into the left sorted array.
Insertion sort is an elementary sorting algorithm. It has a time complexity of Θ(n2), thus being slower than heapsort, merge sort and also shellsort. Insertion sort is well suited for sorting small data sets or for the insertion of new elements into a sorted sequence.
Merge Sort
Merge sort or merge sort is an O(n log n) comparisonbased sorting algorithm. In most implementations it is stable, meaning that it preserves the input order of equal elements in the sorted output.
Quick Sort:
Quicksort sorts by employing a divide and conquer strategy to divide a list into two sublists.
The steps are:
1. Pick an element, called a pivot, from the list.
2. Reorder the list so that all elements which are less than the pivot come before the pivot and so that all elements greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
3. Recursively sort the sublist of lesser elements and the sublist of greater elements.
The base case of the recursion are lists of size zero or one, which are always sorted.
Heap Sort:
A sorting algorithm that works by first organizing the data to be sorted into a special type of binary tree called a heap. The heap itself has, by definition, the largest value at the top of the tree, so the heap sort algorithm must also reverse the order. It does this with the following steps:
1. Remove the topmost item (the largest) and replace it with the rightmost leaf. The topmost item is stored in an array.
2. Reestablish the heap.
3. Repeat steps 1 and 2 until there are no more items left in the heap.
The sorted elements are now stored in an array.
A heap sort is especially efficient for data that is already stored in a binary tree. In most cases, however, the quick sort algorithm is more efficient.
External Sort:
This term is used to refer to sorting methods that are employed when the data to be sorted is too large to fit in primary memory.
1. During the sort, some of the data must be stored externally. Typically the data will be stored on tape or disk.
2. The cost of accessing data is significantly greater than either bookkeeping or comparison costs.
3. There may be severe restrictions on access. For example, if tape is used, items must be accessed sequentially.







Data Structure Theory Tutorial 













