[EdSchouten]

If instead of 'int' you were to use 'size_t' (or the equivalent of that provided by your programming language of choice), then there should be no issues in practice. Then you would only see overflows if your elements were 1 byte in size, and the input spans more than half of the virtual address space. This is unlikely for two reasons:

1. If you only have single byte elements, you'd better use counting sort.

2. There always tend to be parts of the virtual address space that are reserved. On x86-64, most userspace processes can only access 2^47 bytes of space.

[junon]

> input spans more than half of the virtual address space

Not only that, but in practice most general purpose operating systems are designed with higher-half kernels[0].

[0] https://wiki.osdev.org/Higher_Half_Kernel

[valleyer]

32-bit Mac OS X was not (it had a 4/4 scheme).

Though even then I'm not sure you could reliably allocate two gigs of contiguous virtual space without running into some immovable OS-provided thing.