CHAPTER-8

Sorting
 Sorting
Sorting refers to arranging data in a particular format. Sorting algorithm
specifies the way to arrange data in a particular order. Most common orders
are in numerical or lexicographical order.
The importance of sorting lies in the fact that data searching can be optimized
to a very high level, if data is stored in a sorted manner. Sorting is also used
to represent data in more readable formats. Following are some of the
examples of sorting in real-life scenarios
Telephone Directory : The telephone directory stores the telephone numbers
of people sorted by their names, so that the names can be searched easily.

Dictionary: The dictionary stores words in an alphabetical order so that

searching of any word becomes easy.
 Sorting
Sorting is a technique to rearrange the elements of a list in ascending or descending
order, which can be numerical, lexicographical, or any user-defined order.
Sorting is a process through which the data is arranged in ascending or descending
order.
The complexity of a sorting algorithm can be measured in terms of
number of algorithm steps to sort n records
number of comparisons between keys (appropriate when the keys are long character
strings)
number of times record, must be moved (appropriate when record size is large)
Example:
1, 3, 4, 6, 8, 9 are in increasing order, as every next clement is greater than the
previous element
9, 8, 6, 4, 3, 1 are in decreasing order, as every next element is less then the
previous element.
For example, 9, 8, 6, 3, 3, 1 arc in non-increasing order, as every next clement is less
than or equal to (in case of 3) but not greater than any previous element.
For example, 1, 3, 3, 6, 8, 9 are in non-decreasing order, as every next element is
greater than or equal to (in case of 3) but not less than the previous one.
 In-place Sorting and Not-in-place Sorting
Sorting algorithms may require some extra space for comparison
and temporary storage of few data elements. These algorithms
do not require any extra space and sorting is said to happen in-
place, or for example, within the array itself. This is called in-
place sorting. Bubble sort is an example of in-place sorting.

However, in some sorting algorithms, the program requires

space which is more than or equal to the elements being sorted.
Sorting which uses equal or more space is called not-in-place
sorting. Merge-sort is an example of not-in-place sorting.
 Adaptive and Non-Adaptive Sorting Algorithm
A sorting algorithm is said to be adaptive, if it takes advantage
of already 'sorted' elements in the list that is to be sorted. That is,
while sorting if the source list has some element already sorted,
adaptive algorithms will take this into account and will try not to
re-order them.

A non-adaptive algorithm is one which does not take into

account the elements which are already sorted. They try to force
every single element to be re-ordered to confirm their
sortedness.
 Stable and Not Stable Sorting
If a sorting algorithm, after sorting the contents, does not change the sequence of similar
content in which they appear, it is called stable sorting.

If a sorting algorithm, after sorting the contents, changes the sequence of similar content
in which they appear, it is called unstable sorting.
 Internal and External sorting
Internal sorting
An internal sort is any data sorting process that takes place entirely within the main
memory of a computer.
This is possible whenever the data to be sorted is small enough to all be held in the
main memory. There are 3 types of internal sorts.
i) SELECTION SORT:- Ex:- Selection sort algorithm, Heap Sort algorithm
ii) INSERTION SORT:- Ex:- Insertion sort algorithm, Shell Sort algorithm
iii) EXCHANGE SORT:- Ex:- Bubble Sort Algorithm, Quick sort algorithm
External sorting
Sorting large amount of data requires external or secondary memory. This process
uses external memory such as HDD, to store the data which is not fit into the main
memory. So, primary memory holds the currently being sorted data only. All
external sorts are based on process of merging. Different parts of data are sorted
separately and merged together.
Ex:- Merge Sort
 Insertion Sort
The idea behind the insertion sort is that first take one element, iterate it through the sorted array.
Although it is simple to use, it is not appropriate for large data sets as the time complexity of insertion
sort in the average case and worst case is O(n2), where n is the number of items. Insertion sort is less
efficient than the other sorting algorithms like heap sort, quick sort, merge sort, etc.
Insertion sort has various advantages such as:
Simple implementation
Efficient for small data sets
Adaptive, i.e., it is appropriate for data sets that are already substantially sorted.
Algorithm
The simple steps of achieving the insertion sort are listed as follows :
Step 1 - If the element is the first element, assume that it is already sorted. Return 1.
Step2 - Pick the next element, and store it separately in a key.
Step3 - Now, compare the key with all elements in the sorted array.
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 the array is sorted.
 Working
To understand the working of the insertion sort algorithm, let's take an unsorted array. It will
be easier to understand the insertion sort via an example.
Let the elements of array are:

Initially, the first two elements are compared in insertion sort.

Here, 31 is greater than 12. That means both elements are already in ascending order. So, for
now, 12 is stored in a sorted sub-array.

Now, move to the next two elements and compare them.

Here, 25 is smaller than 31. So, 31 is not at correct position. Now, swap 31 with 25. Along
with swapping, insertion sort will also check it with all elements in the sorted array.
 Working
For now, the sorted array has only one element, i.e. 12. So, 25 is greater than 12. Hence, the
sorted array remains sorted after swapping.

Now, two elements in the sorted array are 12 and 25. Move forward to the next elements
that are 31 and 8.

Both 31 and 8 are not sorted. So, swap them.

After swapping, elements 25 and 8 are unsorted.
So, swap them.
Now, elements 12 and 8 are unsorted.
So, swap them too.
Now, the sorted array has three items that are 8, 12 and 25. Move to the next items that are
31 and 32.
Hence, they are already sorted. Now, the sorted array includes 8, 12, 25 and 31.
 Working
Move to the next elements that are 32 and 17.
 Insertion sort complexity
Time Complexity
Best Case Complexity: It occurs when there is no sorting required, i.e. the array is already
sorted. The best-case time complexity of insertion sort is O(n).
Average Case Complexity :It occurs when the array elements are in jumbled order that is not
properly ascending and not properly descending. The average case time complexity of
insertion sort is O(n2).
Worst Case Complexity :It occurs when the array elements are required to be sorted in reverse
order. That means suppose you have to sort the array elements in ascending order, but its
elements are in descending order. The worst-case time complexity of insertion sort is O(n2).
Space Complexity
Space Complexity
O(1)
Stable
YES
The space complexity of insertion sort is O(1). It is because, in insertion sort, an extra variable
is required for swapping.
 selection sort
In selection sort, the smallest value among the unsorted elements of the array is
selected in every pass and inserted to its appropriate position into the array. It is also
the simplest algorithm. It is an in-place comparison sorting algorithm. In this
algorithm, the array is divided into two parts, first is sorted part, and another one is
the unsorted part. Initially, the sorted part of the array is empty, and unsorted part is
the given array. Sorted part is placed at the left, while the unsorted part is placed at
the right.
In selection sort, the first smallest element is selected from the unsorted array and
placed at the first position. After that second smallest element is selected and placed
in the second position. The process continues until the array is entirely sorted.
Selection sort is generally used when :
A small array is to be sorted
Swapping cost doesn't matter
It is compulsory to check all elements
 Selection sort
SELECTION SORT(arr, n) SET SMALL = arr[j]
Step 1: Repeat Steps 2 and 3 for i = 0 to n- SET pos = j
1 [END OF if]
Step 2: CALL SMALLEST(arr, i, n, pos) [END OF LOOP]
Step 3: SWAP arr[i] with arr[pos] Step 4: RETURN pos
[END OF LOOP]
Step 4: EXIT Find the minimum value in the list
Swap it with the value in the first
SMALLEST (arr, i, n, pos) position
Step 1: [INITIALIZE] SET SMALL = Repeat this process for all the elements
arr[i] until the entire array is sorted
Step 2: [INITIALIZE] SET pos = i
Step 3: Repeat for j = i+1 to n
if (SMALL > arr[j])
 Working of Selection sort Algorithm
Let the elements of array are:
Now, for the first position in the sorted array, the entire array is to be scanned
sequentially. At present, 12 is stored at the first position, after searching the entire
array, it is found that 8 is the smallest value.
So, swap 12 with 8. After the first iteration, 8 will appear at the first position in the
sorted array.
For the second position, where 29 is stored presently, we again sequentially scan the
rest of the items of unsorted array. After scanning, we find that 12 is the second
lowest element in the array that should be appeared at second position.

Now, swap 29 with 12. After the second iteration, 12 will appear at the second
position in the sorted array. So, after two iterations, the two smallest values are placed
at the beginning in a sorted way.
The same process is applied to the rest of the array elements. Now, we are showing a
pictorial representation of the entire sorting process.
Working of selection sort
 Selection sort complexity
Time complexity
Best Case Complexity : It occurs when there is no sorting required, i.e. the
array is already sorted. The best-case time complexity of selection sort is
O(n2).
Average Case Complexity: It occurs when the array elements are in
jumbled order that is not properly ascending and not properly descending.
The average case time complexity of selection sort is O(n2).
Worst Case Complexity: It occurs when the array elements are required to
be sorted in reverse order. That means suppose you have to sort the array
elements in ascending order, but its elements are in descending order. The
worst-case time complexity of selection sort is O(n2).
 Bubble Sort
Bubble sort is a simple sorting algorithm. This sorting algorithm is comparison-
based algorithm in which each pair of adjacent elements is compared and the
elements are swapped if they are not in order. This algorithm is not suitable for
large data sets as its average and worst case complexity are of Ο(n2) where n is
the number of items.
Algorithm:
begin BubbleSort(list)

for all elements of list

if list[i] > list[i+1]
swap(list[i], list[i+1])
end if
end for
return list
end BubbleSort
 Working of Bubble sort
Example

Bubble sort starts with very first two elements, comparing them to check which
one is greater.

In this case, value 33 is greater than 14, so it is already in sorted locations. Next,
we compare 33 with 27.

We find that 27 is smaller than 33 and these two values must be swapped.

The new array should look like this:

 Working of Bubble sort
Next we compare 33 and 35. We find that both are in already sorted positions.

Then we move to the next two values, 35 and 10. We know then that 10 is smaller
35. Hence they are not sorted.

We swap these values. We find that we have reached the end of the array. After
one iteration, the array should look like this

To be precise, we are now showing how an array should look like after each
iteration. After the second iteration, it should look like this

Notice that after each iteration, at least one value moves at the end.
 Shell Sort
Shell sort is a highly efficient sorting algorithm and is based on insertion sort algorithm.
This algorithm avoids large shifts as in case of insertion sort, if the smaller value is to the
far right and has to be moved to the far left.
This algorithm uses insertion sort on a widely spread elements, first to sort them and then
sorts the less widely spaced elements. This spacing is termed as interval. This interval is
calculated based on Knuth's formula as.
h=h*3+1
Where: h is interval with initial value 1
This algorithm is quite efficient for medium-sized data sets as its average and worst-case
complexity of this algorithm depends on the gap sequence the best known is Ο(n), where
n is the number of items. And the worst case space complexity is O(n).
Algorithm
Following is the algorithm for shell sort.
Step 1 − Initialize the value of h
Step 2 − Divide the list into smaller sub-list of equal interval h
Step 3 − Sort these sub-lists using insertion sort
Step 3 − Repeat until complete list is sorted
 Shell Sort

Initialize the gap size.

Divide the array into subarrays of equal gap size.
Apply insertion sort on the subarrays.
Repeat the above steps until the gap size becomes O resulting into a sorted array.
If N = 10, the first pass as K = 5 (10/2)
2nd pass k2= k1/2
 Shell Sort Working
Let us consider the following example to have an idea of how shell sort works.
For our example and ease of understanding, we take the interval of 4. Make a
virtual sub-list of all values located at the interval of 4 positions. Here these
values are {35, 14}, {33, 19}, {42, 27} and {10, 44}

We compare values in each sub-list and swap them (if necessary) in the original
array. After this step, the new array should look like this
 Shell Sort Working
Then, we take interval of 1 and this gap generates two sub-lists - {14, 27, 35, 42},
{19, 10, 33, 44}

We compare and swap the values, if required, in the original array. After this step,
the array should look like this:

Finally, we sort the rest of the array using interval of value 1. Shell sort uses
insertion sort to sort the array.
Shell Sort Working
 Merge Sort
If the list is of length O or 1, then it is already sorted. Otherwise:
Divide the unsorted list into two sub lists of about half the size.
Sort each sub list recursively by re-applying merge sort.
Merge the two sub lists back into one sorted list.
Algorithm
Merge sort keeps on dividing the list into equal halves until it can no more be
divided. By definition, if it is only one element in the list, it is sorted. Then, merge
sort combines the smaller sorted lists keeping the new list sorted too.
Step 1 − if it is only one element in the list it is already sorted, return.
Step 2 − divide the list recursively into two halves until it can no more be divided.
Step 3 − merge the smaller lists into new list in sorted order.
 Working of Merge Sort
Merge sort is a sorting technique based on divide and conquer technique. With
worst-case time complexity being Ο(n log n), it is one of the most respected
algorithms.
Merge sort first divides the array into equal halves and then combines them in a
sorted manner.
To understand merge sort, we take an unsorted array as the following:
Unsorted Array

We know that merge sort first divides the whole array iteratively into equal halves
unless the atomic values are achieved. We see here that an array of 8 items is
divided into two arrays of size 4.

This does not change the sequence of appearance of items in the original. Now we
divide these two arrays into halves.
 Working of Merge Sort
further divide these arrays and we achieve atomic value which can no more be
divided.

Now, we combine them in exactly the same manner as they were broken down.
Please note the color codes given to these lists.
We first compare the element for each list and then combine them into another list
in a sorted manner. We see that 14 and 33 are in sorted positions. We compare 27
and 10 and in the target list of 2 values we put 10 first, followed by 27. We
change the order of 19 and 35 whereas 42 and 44 are placed sequentially.

In the next iteration of the combining phase, we compare lists of two data values,
and merge them into a list of found data values placing all in a sorted order.

After the final merging, the list should look like this :
 Quick Sort Algorithm
Quick Sort Algorithm:
Sorting is a way of arranging items in a systematic manner. Quicksort is the widely used
sorting algorithm that makes n log n comparisons in average case for sorting an array of n
elements. It is a faster and highly efficient sorting algorithm. This algorithm follows the
divide and conquer approach. Divide and conquer is a technique of breaking down the
algorithms into sub-problems, then solving the sub-problems, and combining the results
back together to solve the original problem.
Divide: In Divide, first pick a pivot element. After that, partition or rearrange the array
into two sub-arrays such that each element in the left sub-array is less than or equal to the
pivot element and each element in the right sub-array is larger than the pivot element.
Conquer: Recursively, sort two subarrays with Quicksort.
Combine: Combine the already sorted array.
Quicksort picks an element as pivot, and then it partitions the given array around the
picked pivot element. In quick sort, a large array is divided into two arrays in which one
holds values that are smaller than the specified value (Pivot), and another array holds the
values that are greater than the pivot.
After that, left and right sub-arrays are also partitioned using the same approach. It will
continue until the single element remains in the sub-array.
 Quick Sort Algorithm
Choosing the pivot
Picking a good pivot is necessary for the fast implementation of quicksort. However, it is
typical to determine a good pivot. Some of the ways of choosing a pivot are as follows -
Pivot can be random, i.e. select the random pivot from the given array.
Pivot can either be the rightmost element of the leftmost element of the given array.
Select median as the pivot element.
Algorithm:
QUICKSORT (array A, start, end)
{
1 if (start < end)
2{
3 p = partition(A, start, end)
4 QUICKSORT (A, start, p - 1)
5 QUICKSORT (A, p + 1, end)
6}
}
 Quick Sort Algorithm
Working:
Let the elements of array are :
In the given array, we consider the leftmost element as pivot. So, in this case,
a[left] = 24, a[right] = 27 and a[pivot] = 24.
Since, pivot is at left, so algorithm starts from right and move towards left.

Now, a[pivot] < a[right], so algorithm moves forward one position towards left,
i.e.

Now, a[left] = 24, a[right] = 19, and a[pivot] = 24.

Because, a[pivot] > a[right], so, algorithm will swap a[pivot] with a[right], and
pivot moves to right, as -
 Quick Sort Algorithm Working

Now, a[left] = 19, a[right] = 24, and a[pivot] = 24. Since, pivot is at right, so
algorithm starts from left and moves to right.
As a[pivot] > a[left], so algorithm moves one position to right
Now, a[left] = 9, a[right] = 24, and a[pivot] = 24. As a[pivot] > a[left], so
algorithm moves one position to right.
Now, a[left] = 29, a[right] = 24, and a[pivot] = 24. As a[pivot] < a[left], so, swap
a[pivot] and a[left], now pivot is at left, i.e.

Since, pivot is at left, so algorithm starts from right, and move to left. Now, a[left]
= 24, a[right] = 29, and a[pivot] = 24. As a[pivot] < a[right], so algorithm moves
one position to left
 Quick Sort Algorithm Working
Now, a[pivot] = 24, a[left] = 24, and a[right] = 14. As a[pivot] > a[right], so, swap
a[pivot] and a[right], now pivot is at right

Now, a[pivot] = 24, a[left] = 14, and a[right] = 24. Pivot is at right, so the
algorithm starts from left and move to right.

Now, a[pivot] = 24, a[left] = 24, and a[right] = 24. So, pivot, left and right are
pointing the same element. It represents the termination of procedure.
Element 24, which is the pivot element is placed at its exact position.
Elements that are right side of element 24 are greater than it, and the elements that
are left side of element 24 are smaller than it.
 Quick Sort Algorithm Working

Now, in a similar manner, quick sort algorithm is separately applied to the left and
right sub-arrays. After sorting gets done, the array will be

Q. Sort the following array using quick sort

36 34 43 11 15 20 28 45 27 32
 Heap Data structure
Heap is a special Tree-based data structure in which the tree is a complete binary
tree.
There are two types of the heap:
Min Heap:
Max heap:
Min Heap: The value of the parent node should be less than or equal to either of
its children.
Or
In other words, the min-heap can be defined as, for every node i, the value of
node i is greater than or equal to its parent value except the root node.
Mathematically, it can be defined as:
A[Parent(i)] <= A[i]
 Heap Data structure

The value of the parent node is greater than or equal to its children.
Or
In other words, the max heap can be defined as for every node i; the value of node
i is less than or equal to its parent value except the root node. Mathematically, it
can be defined as:
A[Parent(i)] >= A[i]
 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.
Heap sort processes the elements by creating the min heap or max heap using the
elements of the given array.
Min heap or max heap represents the ordering of the array in which root element
represents the minimum or maximum element of the array.
At each step, the root element of the heap gets deleted and stored into the sorted
array and the heap will again be heapified.
The heap sort basically recursively performs two main operations.
 Build a heap H, using the elements of array.
 Repeatedly delete the root element of the heap formed in phase l.
 Heap Sort Algorithm
Sorting can be in ascending or descending order.
Either Max heap or min heap logic can be taken depending on the need.
 Build a max/min heap using Heapify() from the input data.
 At this point, the largest/smallest item is stored at the root of the heap.
Replace it with the last item of the heap followed by reducing the size of
heap by 1. Finally, heapify the root of tree.
 Repeat above steps while size of heap is greater than l.
To sort an unsorted list with 'n' number of elements, following are the complexities ...
Worst Case : O(n log n)
Best Case: O(n log n)
Average Case: O(n log n)
What is meant by Heapify?
Heapify is the process of creating a heap data structure from a binary tree represented
using an array. It is used to create Min-Heap or Max-heap. Start from the first index of the
non-leaf node whose index is given by n/2 – 1. Heapify uses recursion
 Heap Sort working
Consider the array: arr[] = {4, 10, 3, 5, 1}.sort them using heap algorithm:
Step1:
Build a complete binary tree from the array.

Transform into max heap: After that, the task is to construct a tree from that unsorted array and try
to convert it into max heap.
To transform a heap into a max-heap, the parent node should always be greater than or equal to the
child nodes
Here, in this example, as the parent node 4 is smaller than the child node 10, thus, swap them to
build a max-heap.
Transform it into a max heap image widget
Now, as seen, 4 as a parent is smaller than the child 5, thus swap both of these again and the
resulted heap and array should be like this:
 Heap Sort working

Perform heap sort: Remove the maximum element in each step (i.e., move it to the end
position and remove that) and then consider the remaining elements and transform it into
a max heap.
Delete the root element (10) from the max heap. In order to delete this node, try to swap it
with the last node, i.e. (1). After removing the root element, again heapify it to convert it
into max heap.
Resulted heap and array should look like this:
 Heap Sort working

Repeat the above steps and it will look like the following:
Heap Sort working
 Heap Sort working

Now when the root is removed once again it is sorted. and the sorted array will be like
arr[] = {1, 3, 4, 5, 10}.
 Heap Sort working

Q. Sort the following array elements using Heap sort

 Radix Sort
The process of radix sort works similar to the sorting of students names, according to the
alphabetical order. In this case, there are 26 radix formed due to the 26 alphabets in
English. In the first pass, the names of students are grouped according to the ascending
order of the first letter of their names. After that, in the second pass, their names are
grouped according to the ascending order of the second letter of their name. And the
process continues until we find the sorted list.

Algorithm
radixSort(arr)
max = largest element in the given array
d = number of digits in the largest element (or, max)
Now, create d buckets of size 0 - 9
for i -> 0 to d
sort the array elements using counting sort (or any stable sort) according to the digits at
the ith place
 Radix Sort working
First, we have to find the largest element (suppose max) from the given array. Suppose 'x'
be the number of digits in max. The 'x' is calculated because we need to go through the
significant places of all elements.
After that, go through one by one each significant place. Here, we have to use any stable
sorting algorithm to sort the digits of each significant place.
Q. Sort the following array using Radix search.

In the given array, the largest element is 736 that have 3 digits in it. So, the loop will run
up to three times (i.e., to the hundreds place). That means three passes are required to sort
the array.
Now, first sort the elements on the basis of unit place digits (i.e., x = 0). Here, we are
using the counting sort algorithm to sort the elements.
 Radix Sort working
Pass 1:
In the first pass, the list is sorted on the basis of the digits at 0's place.

After the first pass, the array elements are

 Radix Sort working
Pass 2:
In this pass, the list is sorted on the basis of the next significant digits (i.e., digits at 10th
place).

After the second pass, the array elements are

 Radix Sort working
Pass 3:
In this pass, the list is sorted on the basis of the next significant digits (i.e., digits at 100th
place).

After the third pass, the array elements are

 Exchange Sort
An exchange sort is a comparison based sort that has O(N^2) time complexity. It is very
similar to selection sort in that it starts at the beginning of an array or list of items and
compares each successive item to all following items.
When it finds two items whose relative order is incorrect it exchanges the two items. As
the algorithm moves through the list, it ensures every item preceding the current item
being tested is in the correct relative order.
Selection sort uses the same method of traversing the list but does not swap every time an
item is found to be out of order but waits until all subsequent items are examined and just
swaps the current item with the ‘correct’ item.
 Exchange Sort working
Exchange sort:
4 3 2 1 ← starting list seeking to sort in ascending order

3 4 2 1 ← 4 and 3 are exchanged because they are out of order

2 4 3 1 ← 3 and 2 are exchanged because they are out of order

1 4 3 2 ← 2 and 1 are exchanged because they are out of order

Selection sort:
4 3 2 1 ← starting list

4 3 2 1 ← 3 is less than 4 so it is ‘remembered’ as the current least known item

4 3 2 1 ← 2 is less than 3 so it is remembered as the current least known item

4 3 2 1 ← 1 is less than 2 so it is remembered as the current least known item

1 3 2 4 ← 4 and 1 are swapped

 Binary Insertion Sort
Binary insertion sort is a sorting algorithm which is similar to the insertion sort, but
instead of using linear search to find the location where an element should be inserted, we
use binary search. Thus, we reduce the comparative value of inserting a single element
from O (N) to O (log N).
It is a flexible algorithm, which means it works faster when the same given members are
already heavily sorted, i.e., the current location of the feature is closer to its actual
location in the sorted list.
It is a stable filtering algorithm – elements with the same values ​appear in the same
sequence in the last order as they were in the first list.
Applications of Binary Insertion sort:
Binary insertion sort works best when the array has a lower number of items.
When doing quick sort or merge sort, when the subarray size becomes smaller (say <= 25
elements), it is best to use a binary insertion sort.
This algorithm also works when the cost of comparisons between keys is high enough.
For example, if we want to filter multiple strings, the comparison performance of two
strings will be higher.
 Binary Insertion Sort working
In the binary insertion sort mode, we divide the same members into two subarrays –
filtered and unfiltered. The first element of the same members is in the organized
subarray, and all other elements are unplanned.
Then we iterate from the second element to the last. In the repetition of the i-th, we make
the current object our “key”. This key is a feature that we should add to our existing list
below.
In order to do this, we first use a binary search on the sorted subarray below to find the
location of an element larger than our key. Let’s call this position “pos.” We then right
shift all the elements from pos to 1 and created Array[pos] = key.
We can note that in every i-th multiplication, the left part of the array till (i – 1) is already
sorted.
Approach to implement Binary Insertion sort:
Iterate the array from the second element to the last element.
Store the current element A[i] in a variable key.
Find the position of the element just greater than A[i] in the subarray from A[0] to A[i-1]
using binary search. Say this element is at index pos.
Shift all the elements from index pos to i-1 towards the right.
A[pos] = key.
 Efficiency of sorting Algorithm
The complexity of a sorting algorithm measures the running time of a function in which n number
of items are to be sorted.
The choice of sorting method depends on efficiency considerations for different problems.
Tree most important of these considerations are:
 The length of time spent by programmer in coding a particular sorting program
 Amount of machine time necessary for running the program
 The amount of memory necessary for running the program
Various sorting methods are analyzed in the cases like - best case, worst case or average case.
Most of the sort methods we consider have requirements that range from O(nlogn) to O(n2).
A sort should not be selected only because its sorting time is O(nlogn). The relation of the file size
n and the other factors affecting the actual sorting time must be considered
Determining the time requirement of sorting technique is to actually run the program and measure
its efficiency.
Once a particular sorting technique is selected the need is to make the program as efficient as
possible.
Any improvement in sorting time significantly affect the overall efficiency and saves a great deal of
computer time.
Efficiency of sorting Algorithm