What is the best way to sort a vector leaving the original one unaltered?

For the case where you are interested in proxy sorting (sorting an index list), you may want to implement a more flexible algorithm that allows you to deal with containers which do not support random access (such as std::list). For example:

#include <algorithm>
#include <iostream>
#include <list>
#include <numeric>
#include <vector>

template <typename Container>
auto sorted_indices(const Container& c) {
  std::vector<typename Container::size_type> indices(c.size());
  std::iota(indices.begin(), indices.end(), 0);
  std::sort(indices.begin(), indices.end(), [&c](auto lhs, auto rhs) {
    return (*(std::next(c.begin(), lhs)) < *(std::next(c.begin(), rhs)));
  });
  return indices;
}

template <typename Container, typename Indices>
auto display_sorted(const Container& c, const Indices& indices) {
  std::cout << "sorted: ";
  for (auto&& index : indices) {
    std::cout << *(std::next(c.begin(), index)) << " ";
  }
  std::cout << std::endl;
}

template <typename Container>
auto display_sorted(const Container& c) {
  return display_sorted(c, sorted_indices(c));
}

template <typename Container>
auto display(const Container& c) {
  std::cout << "as provided: ";
  for (auto&& ci : c) std::cout << ci << " ";
  std::cout << std::endl;
}

int main() {
  // random access
  const std::vector<int> a{9, 5, 2, 3, 1, 6, 4};
  display(a);
  display_sorted(a);
  display(a);

  std::cout << "---\n";

  // no random access
  const std::list<int> b{9, 5, 2, 3, 1, 6, 4};
  display(b);
  display_sorted(b);
  display(b);
}

Sample run:

$ clang++ example.cpp -std=c++17 -Wall -Wextra
$ ./a.out
as provided: 9 5 2 3 1 6 4 
sorted: 1 2 3 4 5 6 9 
as provided: 9 5 2 3 1 6 4 
---
as provided: 9 5 2 3 1 6 4 
sorted: 1 2 3 4 5 6 9 
as provided: 9 5 2 3 1 6 4 

As you would expect, relying on proxy sorting could have important performance implications. For example: every time you want to traverse in order, you will possibly incur cache misses. In addition, the traversal will have the same complexity as the underlying container for random access: In the case of std::vector, std::next(v.begin(), n) is O(1), but in the case of std::list, std::next(l.begin(), n) is O(n).

Use partial_sort_copy. Here is an example:

vector<int> v{9,8,6,7,4,5,2,0,3,1};
vector<int> v_sorted(v.size());
partial_sort_copy(begin(v), end(v), begin(v_sorted), end(v_sorted));

Now, v remains untouched but v_sorted contains {0,1,2,3,4,5,6,7,8,9}.

As suggested in the comments pass the function argument by value std::vector<int> original:

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

std::vector<int> not_in_place_sort(std::vector<int> original) {
    std::sort(original.begin(), original.end());
    return original;
}

int main() {
    std::vector<int> v = { 8, 6, 7, 2, 3, 4, 1, 5, 9 };
    std::vector<int> v2 = not_in_place_sort(v); // pass the vector by value
    std::cout << "v1: " << '\n';
    for (auto el : v) {
        std::cout << el << ' ';
    }
    std::cout << "\nv2: " << '\n';
    for (auto el : v2) {
        std::cout << el << ' ';
    }
}

That will sort a copy of your original vector leaving the original intact. As pointed out below this might restrict some optimizations such as RVO but will call vector's move constructor in the return statement instead.

Here is my favorite. Sort an index and not the original array/vector itself.

#include <algorithm>

int main() {

    int intarray[4] = { 2, 7, 3, 4 };//Array of values
    //or you can have vector of values as below
    //std::vector<int> intvec = { 2, 7, 3, 4 };//Vector of values
    int indexofarray[4] = { 0, 1, 2, 3 };//Array indices

    std::sort(indexofarray, indexofarray + 4, [intarray](int index_left, int index_right) { return intarray[index_left] < intarray[index_right]; });//Ascending order.
    //have intvec in place of intarray for vector.


}

After this, indexofarray[] elements would be 0, 2, 3, 1, while intarray[] is unchanged.