3 ms·
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 prac
by EdSchouten 4y ago
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.
- deleted 4y ago[deleted]
- junon 4y ago> 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 https://wiki.osdev.org/Higher_Half_Kernel
- valleyer 4y ago32-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.
- deleted 4y ago[deleted]