Question

Data Structure and Algorithm:

1. You are asked to use insertion sort to sort a singly linked list in ascending order. Why is this a bad idea? How does insertion sort’s runtime complexity change if you were to use it to sort a linked list?

2. Your classmate thinks that input arrays to the merge operation of merge sort don’t need to be in sorted order. Is your classmate right or wrong? Why?

Answer 1

1.

Insertion sort splits an array into 3 parts as the current element, sorted part and an unsorted part.Sorted part inclueds the elements prior to the current element and unsorted part inculdes elements next to the current element.

The current element is compared against each of its previous elements in the sorted part and greater elements are moved one position up to make space for the currrent element.

Performing insertion sort on singly linked lists will be a bad idea ,since singly linked lists can be traversed in forward direction only and not in backward direction.

2.

The classmate is wrong .

Input arrays to the merge operation of merge sort needs to be in sorted order ,otherwise the runtime may furthur increase.

In merge sort, an array is divided into two smaller subarrays recursively till a single element is reached and then the subarrays are compared and merged.Let's see an example,

Consider the array with values {14,8,9,24,5,1}

Now after the divide step is completed, the resulting sub arrays are combined as follows,

Here at each step, elements of a subarray are compared against elements of another subarray while getting merged , since each subarray is sorted.If the subarrays were unsorted ,the elements within each subarray might have to be compared against one another too.And this have to be repeated at each step and the time taken for merge sort will be higher.

When the input arrays to the merge operation are sorted , number of comparisons of elements needs to be performed at each step decreases tremendously and hence the time required to perform merge sort also decreases.

So, input arrays to the the merge operation of merge sort needs to be in sorted order.