Sorting an Array with duplicates using Insertion sort

Question

package com.sort;

public class ArraySel {

    private Long[] a;
    private int nElems;

    public ArraySel(int max)
    {
        a = new Long[max];
        nElems = 0;
    }

    public void insert(long max)
    {
        a[nElems] = max;
        nElems++;
    }

    public void display()
    {
        for(int j = 0; j < nElems; j++)
        {
            System.out.print(a[j]+ "  ");
        }
        System.out.println();
    }

    public void insertionSort()
    {
        int in , out, flag = 0;
        long temp;
        for(out = 1; out < nElems; out++)
        {
            temp = a[out];
            in = out;
            while(in > 0 && a[in - 1] >= temp )
            {
                if(a[in] == a[in - 1 ])
                {
                    flag++;
                    in--;
                }
                else
                {
                    a[in] = a[in-1];
                    in--;
                }
            }
            a[in] = temp;
        }
    }

}

This code takes an unsorted array and sorts it using Insertion Sort. When duplicates are arranged together in unsorted array then due to multiple shifting complexity raises to O(N^2) , which i tried to make it O(N) by making sure no item moved more than once in case of duplicates arranged together.

But when duplicates are not arranged together complexity remains O(N^2). Can we make the complexiy O(N) in this case too ?

Answer 1

Without further information about the underlying data, the best time complexity you can achieve with sorting algorithms is O(n log n) (n being the number of elements).

Sorting algorithms like insertion sort, bubble sort, selection sort, etc., all have a time complexity of O(n²) due to their double loops. In fact they sometimes tend to work better, when getting an already sorted list of elements. Insertion sort for example has a time complexity of O(n) for a completely sorted list.

There is nothing you can do to change the inherent time complexity of those algorithms. The only thing you can do is short-cutting the algorithm when finding pre-sorted regions in the incoming list.