Is my Insertion Sort optimal?

Question

I'm learning sorting algorithms and wrote my own implementation of Insertion Sort. Is it optimal? Is there anything that can be done better?

#include <iostream>
#include <vector>
#include <algorithm>
#include <vector>

void display(std::vector<int> arr)
{
  for (int i = 0; i < arr.size(); ++i)
    {
      std::cout << arr[i] << ' ';
    }
  std::cout << std::endl;
}

std::vector<int>& insertionSort(std::vector<int>& arr)
{
  int i = 1;
  while (i < arr.size())
    {
      int j = i;
      while ((j > 0) && (arr[j-1] > arr[j]))
    {
      std::swap(arr[j-1],arr[j]);
      --j;
    }
      ++i;
    }
  return arr;
}  

int main()
{
  std::vector<int> arr{1,4,3,5,6,2};
  display(insertionSort(arr));
  return 0;
}

Answer 1

  int i = 1;
  while (i < arr.size())
    {
      // body of loop
      ++i;
    }

That is the quintessential for loop. Write it as:

const auto ASize = arr.size();
for (size_t i= 1;  i < ASize;  ++i) {
   // body of loop
}

I also saved the array size since it doesn't change... but your variable arr is not const and the compiler can't really deduce that it doesn't change so it will call the function every time. (OTOH, the inlined size() function might be simple enough that it's just as fast as a variable, but generally we don't assume this)

Meanwhile, you are comparing a signed and unsigned value, which should be giving you a warning. Make i the same type as the thing it is compared against.

frozenca shows the main loop written as two calls to existing STL algorithms, which is indeed the way it ought to be written today. This means understanding what those algorithms do.

Back in the day, implementing sorts from scratch as part of learning how sorting works, I didn't have library calls that did so much of the work. To really show how it works "from scratch" you should write a binary search and insert code too. You step back one element at a time (not a binary search) and swap every pair as you go; it is more optimal to find the insertion position using a binary search and then move them all with one call. The former changes the complexity from n/2 comparisons to log n comparisons, and thus the whole sort from O (n²) to O (n log n), which is an important detail! The latter does not change the formal complexity but is much faster (by a constant factor).

(Actually, I did use a built-in library call when implementing the binary tree sort; this was a machine language primitive used by the system's own compiler and tools! The instructor had me re-write to actually do all the primitive manipulations, to show that I understood what it was doing.)

Since you are sorting in-place, you don't really care that you have a std::vector. You should accept two iterators in the same manner as the standard algorithms, and then the same code can sort std::vector, a plain array, or anything that has suitable iterators.

So, don't use subscript index values i and j, but use two iterators instead, when doing the work.

Using iterators, you can sort a subrange of a collection as well, which is very useful when you write the more advanced sorts: For example, when a quicksort gets down to a small enough span it calls the simple insertion sort instead.

Answer 2

Your insertionSort() is OK, but I would write:

template<std::forward_iterator Iter>
void insertion_sort(Iter first, Iter last) {
    for (Iter it = first; it != last; ++it)
        std::rotate(std::upper_bound(first, it, *it), it, std::next(it));
}

insertion_sort(v.begin(), v.end());

display() copys your vector, so make the parameter as const (lvalue) reference.

Use ranged-for loop for printing:

for (auto n : vec) {
    std::cout << n << ' ';
}
std::cout << '\n'; // don't use std::endl

Or you can use one-liner

std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, ' '));