Sorting means arranging the elements of an array so that they are placed in some
relevant order which may be either ascending or descending.
Sorting can be done based on key references which can be numbers, alphabets etc.
if A is an array, then the elements of A are arranged in a sorted order (ascending order)
in such a way that A[0] < A[1] < A[2] < ...... < A[N-1].
For example, if we have an array that is declared and initialized as
A[] = {21, 34, 11, 9, 1, 0, 22};
Then the sorted array (ascending order) can be given as: A[] = {0, 1, 9, 11, 21, 22, 34};
Examples of sorting in real life scenarios :
o Telephone directories in which names are sorted by location, category (business
or residential), and then in an alphabetical order.
o In a library, the information about books can be sorted alphabetically based on
titles and then by authors’ names.
o Customers’ addresses can be sorted based on the name of the city and then the
street.
Sorting can be categorized in two different categories:
Types of sorting:
1. Internal Sorting:
The sorting is done within the computer main memory and all the data to be
sorted is stored in main memory.
It is performed when the data to be sorted is small enough to fit in main
memory. (It is used when the size of input is small.)
In it, the storage device used is only main memory (RAM).
Examples: Insertion sort, Quick Sort, Bubble Sort, etc.
2. External Sorting:
The sorting is done in external file disk and data is stored outside the main
memory like on disk and only loaded into memory in small chunks.
It is usually applied when data can’t fit in main memory entirely. (It is used when
the size of input is large.)
In it, the storage device used are main memory (RAM) and secondary memory
(Hard Disk).
Examples: External Merge Sort, External Radix Sort, Four Tape Sort.
[Shankar Bhandari][IOE][Sagarmatha Engineering College]
Insertion sort:
Insertion sort is implemented by inserting a particular data item in its proper
position.
Any unsorted data item is kept on swapping with its previous data items until its
proper position is not found.
The number of swapping makes the previous data items to shift for the new data
item to take its position in order.
Once the new data item is inserted, the next data item after it is chosen for next
insertion.
The process continues until all data items are sorted.
We all are familiar with this technique of sorting, as we usually use it for ordering
a deck of cards.
It is efficient for smaller data sets, but very inefficient for larger lists.
Less efficient as compared to other more advanced algorithms such as quick
Sort, heap sort, and merge sort.
[Shankar Bhandari][IOE][Sagarmatha Engineering College]
Algorithm:
Step 1 - If it is the first element, it is already sorted. Return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − If the element in the sorted array is smaller than the current element,
then move to the next element. Else, shift greater elements in the array towards
the right.
Step 5 − Insert the value
Step 6 − Repeat until list is sorted
//𝑰𝒏𝒔𝒆𝒓𝒕𝒊𝒐𝒏 𝒔𝒐𝒓𝒕 𝒍𝒐𝒈𝒊𝒄
𝐅𝐨𝐫( 𝐢 = 𝟏 ; 𝐢 < 𝐬𝐢𝐳𝐞 ; 𝐢 + +)
{
𝐭𝐞𝐦𝐩 = 𝐥𝐢𝐬𝐭[𝐢];
𝐣 = 𝐢 − 𝟏;
𝐰𝐡𝐢𝐥𝐞 ((𝐭𝐞𝐦𝐩 < 𝐥𝐢𝐬𝐭[𝐣])&& (𝐣 ≥ 𝟎))
{
𝐥𝐢𝐬𝐭[𝐣 + 𝟏] = 𝐥𝐢𝐬𝐭[𝐣];
𝐣 = 𝐣 − 𝟏;
}
𝐥𝐢𝐬𝐭[𝐣 + 𝟏] = 𝐭𝐞𝐦𝐩;
}
Example 1:
Efficiency:
Nested loops
Worst Case : O(n2)
Best Case : Ω(n)
Average Case : Θ(n2)
[Shankar Bhandari][IOE][Sagarmatha Engineering College]
Example 2:
[Shankar Bhandari][IOE][Sagarmatha Engineering College]
Selection Sort:
Selection Sort algorithm is an in-place comparison-based algorithm in which the list is divided
into two parts, the sorted part at the left end and the unsorted part at the right end. Initially,
the sorted part is empty and the unsorted part is the entire list.
The smallest element is selected from the unsorted array and swapped with the leftmost
element, and that element becomes a part of the sorted array. This process continues moving
unsorted array boundary by one element to the right.
Algorithm:
Step 1 − Set MIN to location 0
Step 2 − Search the minimum element in the list
Step 3 − Swap with value at location MIN
Worst Case : O(n2)
Step 4 − Increment MIN to point to next element
Best Case : Ω(n2)
Step 5 − Repeat until list is sorted Average Case : Θ(n2)
Example 1:
[Shankar Bhandari][IOE][Sagarmatha Engineering College]
Example 2:
Bubble Sort/ Exchange sort:
a simple sorting algorithm which
o repeatedly steps through the list to be sorted
o compares each pair of adjacent items
o swaps them if they are in the wrong order
o The passing through the list is continued until the swapping is not required (i.e.
the list sorted)
it is a comparison sort
It is called Bubble Sort because the data gradually bubbles up in its proper position
In each pass at least one data is bubbled up in its proper position
[Shankar Bhandari][IOE][Sagarmatha Engineering College]
Example: 6 1 3 2 7
First Pass:
( 𝟔 𝟏 3 2 7 )( 𝟏 𝟔 3 2 7 ), 𝑆𝑤𝑎𝑝 𝑠𝑖𝑛𝑐𝑒 6 > 1.
( 1 𝟔 𝟑 2 7 )( 1 𝟑 𝟔 2 7 ), 𝑆𝑤𝑎𝑝 𝑠𝑖𝑛𝑐𝑒 6 > 3
( 1 3 𝟔 𝟐 7 )( 1 3 𝟐 𝟔 7 ), 𝑆𝑤𝑎𝑝 𝑠𝑖𝑛𝑐𝑒 6 > 2
( 1 3 2 𝟔 𝟕 ), 𝑑𝑜𝑒𝑠 𝑛𝑜𝑡 𝑠𝑤𝑎𝑝
Second Pass:
(𝟏𝟑267)
( 1 𝟑 𝟐 6 7 )( 1 𝟐 𝟑 6 7 ), 𝑆𝑤𝑎𝑝 𝑠𝑖𝑛𝑐𝑒 3 > 2
( 1 2 𝟑 𝟔 7 )( 1 2 𝟑 𝟔 7 )
(123𝟔𝟕)
List is already sorted, but our algorithm does not know. Hence one more pass to
see if further swapping has to be done
Third Pass:
( 1 2 3 6 7), No swap up to the last comparison, hence the list is sorted
Algorithm:
The basic methodology of the working of bubble sort is given as follows:
(𝑎)𝐼𝑛 𝑃𝑎𝑠𝑠 1, 𝐴[0]𝑎𝑛𝑑 𝐴[1]𝑎𝑟𝑒 𝑐𝑜𝑚𝑝𝑎𝑟𝑒𝑑, 𝑡ℎ𝑒𝑛 𝐴[1]𝑖𝑠 𝑐𝑜𝑚𝑝𝑎𝑟𝑒𝑑 𝑤𝑖𝑡ℎ 𝐴[2],
𝐴[2]𝑖𝑠 𝑐𝑜𝑚𝑝𝑎𝑟𝑒𝑑 𝑤𝑖𝑡ℎ 𝐴[3], 𝑎𝑛𝑑 𝑠𝑜 𝑜𝑛. 𝐹𝑖𝑛𝑎𝑙𝑙𝑦, 𝐴[𝑁– 2]𝑖𝑠 𝑐𝑜𝑚𝑝𝑎𝑟𝑒𝑑 𝑤𝑖𝑡ℎ 𝐴[𝑁– 1].
𝑃𝑎𝑠𝑠 1 𝑖𝑛𝑣𝑜𝑙𝑣𝑒𝑠 𝑛– 1 𝑐𝑜𝑚𝑝𝑎𝑟𝑖𝑠𝑜𝑛𝑠 𝑎𝑛𝑑 𝑝𝑙𝑎𝑐𝑒𝑠 𝑡ℎ𝑒 𝑏𝑖𝑔𝑔𝑒𝑠𝑡 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 𝑎𝑡 𝑡ℎ𝑒
ℎ𝑖𝑔ℎ𝑒𝑠𝑡 𝑖𝑛𝑑𝑒𝑥 𝑜𝑓 𝑡ℎ𝑒 𝑎𝑟𝑟𝑎𝑦.
(𝑏)𝐼𝑛 𝑃𝑎𝑠𝑠 2, 𝐴[0]𝑎𝑛𝑑 𝐴[1]𝑎𝑟𝑒 𝑐𝑜𝑚𝑝𝑎𝑟𝑒𝑑, 𝑡ℎ𝑒𝑛 𝐴[1]𝑖𝑠 𝑐𝑜𝑚𝑝𝑎𝑟𝑒𝑑 𝑤𝑖𝑡ℎ 𝐴[2],
𝐴[2]𝑖𝑠 𝑐𝑜𝑚𝑝𝑎𝑟𝑒𝑑 𝑤𝑖𝑡ℎ 𝐴[3], 𝑎𝑛𝑑 𝑠𝑜 𝑜𝑛. 𝐹𝑖𝑛𝑎𝑙𝑙𝑦, 𝐴[𝑁– 3]𝑖𝑠 𝑐𝑜𝑚𝑝𝑎𝑟𝑒𝑑 𝑤𝑖𝑡ℎ 𝐴[𝑁– 2].
𝑃𝑎𝑠𝑠 2 𝑖𝑛𝑣𝑜𝑙𝑣𝑒𝑠 𝑛– 2 𝑐𝑜𝑚𝑝𝑎𝑟𝑖𝑠𝑜𝑛𝑠 𝑎𝑛𝑑 𝑝𝑙𝑎𝑐𝑒𝑠 𝑡ℎ𝑒 𝑠𝑒𝑐𝑜𝑛𝑑 𝑏𝑖𝑔𝑔𝑒𝑠𝑡 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 𝑎𝑡 𝑡ℎ𝑒
𝑠𝑒𝑐𝑜𝑛𝑑 ℎ𝑖𝑔ℎ𝑒𝑠𝑡 𝑖𝑛𝑑𝑒𝑥 𝑜𝑓 𝑡ℎ𝑒 𝑎𝑟𝑟𝑎𝑦.
(𝑐) 𝐼𝑛 𝑃𝑎𝑠𝑠 𝑛– 1, 𝐴[0] 𝑎𝑛𝑑 𝐴[1] 𝑎𝑟𝑒 𝑐𝑜𝑚𝑝𝑎𝑟𝑒𝑑 𝑠𝑜 𝑡ℎ𝑎𝑡 𝐴[0].
Efficiency:
Nested loops and for n items, n possible swaps
Worst Case : O(n2)
Best Case : Ω(n2)
Average Case : Θ(n2)
[Shankar Bhandari][IOE][Sagarmatha Engineering College]
Example 1:
[Shankar Bhandari][IOE][Sagarmatha Engineering College]
Merge sort:
It is a divide and conquer algorithm
At first we divide the given list of item
o list is divided into two parts from middle
o The process is repeated until each sub list contain exactly 1 item
Now is the turn for sort and combine (conquer)
o A list with a single element is considered sorted automatically
o Pair of list is sorted and merged into one (i.e. approx. n/2 sub lists of size 2)
o The sort and merge is keep on repeated until a single list of size n is found
The overall dividing and conquering is done recursively
To sort A[p .... r]: (p=starting index , r=ending index)
Divide Step:
If a given array A has zero or one element, simply return; it is already sorted.
Otherwise, split A [p ... r] into two sub arrays A [p ... q] and A [q + 1 … r], each containing
about half of the elements of A [p ... r]. That is,
q is the halfway point of A[p .. r].
Conquer Step
Conquer by recursively sorting the two sub arrays A [p ... q] and A [q + 1 … r].
[Shankar Bhandari][IOE][Sagarmatha Engineering College]
Combine Step
Combine the elements back in A [p … r] by merging the two sorted sub arrays A [p ... q]
and A [q + 1 ... r] into a sorted sequence.
To accomplish this step, we will define a procedure MERGE (A, p, q, r).
Divide Conquer
Efficiency:
Divide and conquer (tree structure) : log n
However n sub-lists need to be sorted
𝑾𝒐𝒓𝒔𝒕 𝑪𝒂𝒔𝒆 ∶ 𝑶(𝑛 ∗ 𝑙𝑜𝑔𝑛)
𝑩𝒆𝒔𝒕 𝑪𝒂𝒔𝒆 ∶ 𝑂( 𝑛 ∗ 𝑙𝑜𝑔𝑛 )
𝑨𝒗𝒆𝒓𝒂𝒈𝒆 𝑪𝒂𝒔𝒆 ∶ 𝑂( 𝑛 ∗ 𝑙𝑜𝑔𝑛 )
[Shankar Bhandari][IOE][Sagarmatha Engineering College]
Example 1:
Redix sort:
Radix sort is the linear sorting algorithm that is used for integers. In Radix sort, there is digit by
digit sorting is performed that is started from the least significant digit to the most significant
digit.
The process of radix sort works similar to the sorting of students names, according to the
alphabetical order.
Algorithm:
Step 1 – Find largest element in the given array and number of digits in the largest element.
Step 2 - Define 10 queues each representing a bucket for each digit from 0 to 9.
Step 3 - Consider the least significant digit of each number in the list which is to be sorted.
Step 4 - Insert each number into their respective queue based on the least significant digit.
Step 5 - Group all the numbers from queue 0 to queue 9 in the order they have inserted into
their respective queues.
Step 6 - Repeat from step 4 based on the next least significant digit.
Step 7 - Repeat from step 3 until all the numbers are grouped based on the most significant
digit.
[Shankar Bhandari][IOE][Sagarmatha Engineering College]
Example 1: 𝑾𝒐𝒓𝒔𝒕 𝑪𝒂𝒔𝒆 ∶ 𝑶(𝑛)
𝑩𝒆𝒔𝒕 𝑪𝒂𝒔𝒆 ∶ 𝑶( 𝑛 )
𝑨𝒗𝒆𝒓𝒂𝒈𝒆 𝑪𝒂𝒔𝒆 ∶ 𝑶( 𝑛 )
[Shankar Bhandari][IOE][Sagarmatha Engineering College]
Shell sort:
Shell sort is the generalization of insertion sort, which overcomes the drawbacks of insertion
sort by comparing elements separated by a gap of several positions.
It first sorts elements that are far apart from each other by swapping and successively reduces
the gap between the elements to be sorted. This gap is called as interval. The interval between
the elements is reduced based on the sequence used. Some of the optimal sequences that can
be used in the shell sort algorithm are:
Shell′s original sequence: N/2 , N/4 , … , 1
Knuth′s Formula = h ∗ 3 + 1 where − h is interval with initial value 1
Hibbard′s increments: 1, 3, 7, 15, 31, 63, 127, 255, 511 …
Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81. . . .
Algorithm: Best Case: O(n*log n)
Average Case: O(n*log n)
Step 1 − for the size of array ‘N’.
Worst Case: O(n2)
Step 2 − Divide the list into smaller sub-list of interval N/2.
Step 3 − Sort these sub-lists using insertion sort.
Step 3 − Repeat until complete list is sorted.
Shell Sort(a, n) // 'a' is the given array, 'n' is the size of array
𝑓𝑜𝑟 (𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙 = 𝑛/2; 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙 >= 1; 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙 /= 2)
𝑓𝑜𝑟 ( 𝑗 = 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙; 𝑗 < 𝑛; 𝑗 + +)
𝑓𝑜𝑟 (𝑖 = 𝑗 − 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙; 𝑖 >= 0; 𝑖 −= 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙)
𝑖𝑓 ( 𝑎[𝑖 + 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙] > 𝑎[𝑖] )
o 𝑏𝑟𝑒𝑎𝑘
𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
o 𝑠𝑤𝑎𝑝 ( 𝑎[𝑖 + 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙], 𝑎[𝑖] )
𝐸𝑛𝑑 𝑆ℎ𝑒𝑙𝑙 𝑆𝑜𝑟𝑡
Example:
Let the elements of array are –
We will use the original sequence of shell sort, i.e., N/2, N/4...1 as the intervals.
Here, in the first loop, the element at the 0th position will be compared with the element at
4th position. If the 0th element is greater, it will be swapped with the element at 4th position.
Otherwise, it remains the same. This process will continue for the remaining elements.
[Shankar Bhandari][IOE][Sagarmatha Engineering College]
At the interval of 4, the sub lists are {33, 12}, {31, 17}, {40, 25}, {8, 42}.
After comparing and swapping, the updated array will look as follows –
In the second loop, elements are lying at the interval of 2 (n/4 = 2), where n = 8.
After comparing and swapping, the updated array will look as follows –
In the third loop, elements are lying at the interval of 1 (n/8 = 1), where n = 8.
[Shankar Bhandari][IOE][Sagarmatha Engineering College]
Heap sort as a priority queue:
Heap sort is one of the sorting algorithms used to arrange a list of elements in order. Heap sort
algorithm uses one of the tree concepts called Heap Tree. The concept of heap sort is to eliminate the
elements one by one from the heap part of the list, and then insert them into the sorted part of the list.
Heap sort is the in-place sorting algorithm.
Algorithm:
Step 1 - Construct a Binary Tree with given list of Elements.
Step 2 - Transform the Binary Tree into Max Heap.
Step 3 - Delete the root element from Max Heap using Heapify method.
Step 4 - Put the deleted element into the Sorted list.
Step 5 - Repeat the same until Max Heap becomes empty.
Step 6 - Display the sorted list.
Heapify (a, n) // 'a' is the given array, 'n' is the size of array
𝑾𝒐𝒓𝒔𝒕 𝑪𝒂𝒔𝒆 ∶ 𝑶(𝑛 𝑙𝑜𝑔 𝑛)
𝑩𝒆𝒔𝒕 𝑪𝒂𝒔𝒆 ∶ 𝑶(𝑛 𝑙𝑜𝑔 𝑛)
𝑨𝒗𝒆𝒓𝒂𝒈𝒆 𝑪𝒂𝒔𝒆 ∶ 𝑶(𝑛 𝑙𝑜𝑔 𝑛)
[Shankar Bhandari][IOE][Sagarmatha Engineering College]
Example 1:
[Shankar Bhandari][IOE][Sagarmatha Engineering College]
Big ‘O’ notation and Efficiency of sorting:
Big - Oh notation is used to define the upper bound of an algorithm in terms of Time
Complexity. That means Big - Oh notation always indicates the maximum time required by an
algorithm for all input values. That means Big - Oh notation describes the worst case of an
algorithm time complexity.
Big-O Analysis of Algorithms:
We can express algorithmic complexity using the big-O notation. For a problem of size N:
A constant-time function/method is “order 1” : O(1)
A linear-time function/method is “order N” : O(N)
A quadratic-time function/method is “order N squared” : O(N 2 )
[Shankar Bhandari][IOE][Sagarmatha Engineering College]
The general step wise procedure for Big-O runtime analysis is as follows:
1. Figure out what the input is and what n represents.
2. Express the maximum number of operations, the algorithm performs in terms of n.
3. Eliminate all excluding the highest order terms.
4. Remove all the constant factors.
Runtime Analysis of Algorithms:
𝐴 𝑙𝑜𝑔𝑎𝑟𝑖𝑡ℎ𝑚𝑖𝑐 𝑎𝑙𝑔𝑜𝑟𝑖𝑡ℎ𝑚 – 𝑂(𝑙𝑜𝑔𝑛)
𝑅𝑢𝑛𝑡𝑖𝑚𝑒 𝑔𝑟𝑜𝑤𝑠 𝑙𝑜𝑔𝑎𝑟𝑖𝑡ℎ𝑚𝑖𝑐𝑎𝑙𝑙𝑦 𝑖𝑛 𝑝𝑟𝑜𝑝𝑜𝑟𝑡𝑖𝑜𝑛 𝑡𝑜 𝑛.
𝐴 𝑙𝑖𝑛𝑒𝑎𝑟 𝑎𝑙𝑔𝑜𝑟𝑖𝑡ℎ𝑚 – 𝑂(𝑛)
𝑅𝑢𝑛𝑡𝑖𝑚𝑒 𝑔𝑟𝑜𝑤𝑠 𝑑𝑖𝑟𝑒𝑐𝑡𝑙𝑦 𝑖𝑛 𝑝𝑟𝑜𝑝𝑜𝑟𝑡𝑖𝑜𝑛 𝑡𝑜 𝑛.
𝐴 𝑠𝑢𝑝𝑒𝑟𝑙𝑖𝑛𝑒𝑎𝑟 𝑎𝑙𝑔𝑜𝑟𝑖𝑡ℎ𝑚 – 𝑂(𝑛𝑙𝑜𝑔𝑛)
𝑅𝑢𝑛𝑡𝑖𝑚𝑒 𝑔𝑟𝑜𝑤𝑠 𝑖𝑛 𝑝𝑟𝑜𝑝𝑜𝑟𝑡𝑖𝑜𝑛 𝑡𝑜 𝑛.
𝐴 𝑝𝑜𝑙𝑦𝑛𝑜𝑚𝑖𝑎𝑙 𝑎𝑙𝑔𝑜𝑟𝑖𝑡ℎ𝑚 – 𝑂(𝑛𝑐 )
𝑅𝑢𝑛𝑡𝑖𝑚𝑒 𝑔𝑟𝑜𝑤𝑠 𝑞𝑢𝑖𝑐𝑘𝑒𝑟 𝑡ℎ𝑎𝑛 𝑝𝑟𝑒𝑣𝑖𝑜𝑢𝑠 𝑎𝑙𝑙 𝑏𝑎𝑠𝑒𝑑 𝑜𝑛 𝑛.
𝐴 𝑒𝑥𝑝𝑜𝑛𝑒𝑛𝑡𝑖𝑎𝑙 𝑎𝑙𝑔𝑜𝑟𝑖𝑡ℎ𝑚 – 𝑂(𝑐 𝑛 )
𝑅𝑢𝑛𝑡𝑖𝑚𝑒 𝑔𝑟𝑜𝑤𝑠 𝑒𝑣𝑒𝑛 𝑓𝑎𝑠𝑡𝑒𝑟 𝑡ℎ𝑎𝑛 𝑝𝑜𝑙𝑦𝑛𝑜𝑚𝑖𝑎𝑙 𝑎𝑙𝑔𝑜𝑟𝑖𝑡ℎ𝑚 𝑏𝑎𝑠𝑒𝑑 𝑜𝑛 𝑛.
𝐴 𝑓𝑎𝑐𝑡𝑜𝑟𝑖𝑎𝑙 𝑎𝑙𝑔𝑜𝑟𝑖𝑡ℎ𝑚 – 𝑂(𝑛!)
𝑅𝑢𝑛𝑡𝑖𝑚𝑒 𝑔𝑟𝑜𝑤𝑠 𝑡ℎ𝑒 𝑓𝑎𝑠𝑡𝑒𝑠𝑡 𝑎𝑛𝑑 𝑏𝑒𝑐𝑜𝑚𝑒𝑠 𝑞𝑢𝑖𝑐𝑘𝑙𝑦 𝑢𝑛𝑢𝑠𝑎𝑏𝑙𝑒 𝑓𝑜𝑟 𝑒𝑣𝑒𝑛
𝑠𝑚𝑎𝑙𝑙 𝑣𝑎𝑙𝑢𝑒𝑠 𝑜𝑓 𝑛.
[Shankar Bhandari][IOE][Sagarmatha Engineering College]
Algorithmic Examples of Runtime Analysis:
𝐿𝑜𝑔𝑎𝑟𝑖𝑡ℎ𝑚𝑖𝑐 𝑎𝑙𝑔𝑜𝑟𝑖𝑡ℎ𝑚 – 𝑂(𝑙𝑜𝑔𝑛) – 𝐵𝑖𝑛𝑎𝑟𝑦 𝑆𝑒𝑎𝑟𝑐ℎ.
𝐿𝑖𝑛𝑒𝑎𝑟 𝑎𝑙𝑔𝑜𝑟𝑖𝑡ℎ𝑚 – 𝑂(𝑛) – 𝐿𝑖𝑛𝑒𝑎𝑟 𝑆𝑒𝑎𝑟𝑐ℎ.
𝑆𝑢𝑝𝑒𝑟 𝑙𝑖𝑛𝑒𝑎𝑟 𝑎𝑙𝑔𝑜𝑟𝑖𝑡ℎ𝑚 – 𝑂(𝑛𝑙𝑜𝑔𝑛) – 𝐻𝑒𝑎𝑝 𝑆𝑜𝑟𝑡, 𝑀𝑒𝑟𝑔𝑒 𝑆𝑜𝑟𝑡.
𝑃𝑜𝑙𝑦𝑛𝑜𝑚𝑖𝑎𝑙 𝑎𝑙𝑔𝑜𝑟𝑖𝑡ℎ𝑚 – 𝑂(𝑛^𝑐) – 𝐵𝑢𝑏𝑏𝑙𝑒 𝑆𝑜𝑟𝑡, 𝑆𝑒𝑙𝑒𝑐𝑡𝑖𝑜𝑛 𝑆𝑜𝑟𝑡, 𝐼𝑛𝑠𝑒𝑟𝑡𝑖𝑜𝑛 𝑆𝑜𝑟𝑡, 𝐵𝑢𝑐𝑘𝑒𝑡 𝑆𝑜𝑟𝑡.
𝐸𝑥𝑝𝑜𝑛𝑒𝑛𝑡𝑖𝑎𝑙 𝑎𝑙𝑔𝑜𝑟𝑖𝑡ℎ𝑚 – 𝑂(𝑐^𝑛) – 𝑇𝑜𝑤𝑒𝑟 𝑜𝑓 𝐻𝑎𝑛𝑜𝑖.
𝐹𝑎𝑐𝑡𝑜𝑟𝑖𝑎𝑙 𝑎𝑙𝑔𝑜𝑟𝑖𝑡ℎ𝑚 – 𝑂(𝑛!) – 𝐷𝑒𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑛𝑡 𝐸𝑥𝑝𝑎𝑛𝑠𝑖𝑜𝑛 𝑏𝑦 𝑀𝑖𝑛𝑜𝑟𝑠.
[Shankar Bhandari][IOE][Sagarmatha Engineering College]