Efficient sorting mechanism for Unsorted Array – List Insertion Sort

You can use sorted linked list as a sorting mechanism in some situations. Let us say you have an array of unsorted items. You copy items one by one from array and insert them one by one in to the sorted linked list. The end result is they all will be placed in sorted order automatically. This mechanism is called List Insertion Sort.

List Insertion Sort Example

Note: insert() method accepts a Link object as an argument. So that we can store Link objects in the array and directly insert them in to the sorted linked list.

Output:

Efficiency of List Insertion Sort

This type of sorting mechanism is more efficient than Simple Sorting (Insertion sort within an array) because only fewer copies are necessary in this case i.e., N copies (for items that are copied only once from array to the list) and one more N copies (for items that are copied only once from list to the array). So total N*2 copies compared to insertion sort within an array, where it requires N2 copies.

Drawbacks of list insertion sort

The drawback of list insertion sort is it takes somewhat more than twice as much memory than the array-based insertion sort. The array and linked list must be in memory at the same time.

Recommended Posts

References

Leave a Reply

avatar
  Subscribe  
Notify of