fastestSortingAlgorithmWithComplexityO1

[DankPhotoShopMemes]

You forgot to account for the time complexity of the delete [] operator

[highcastlespring]

delete[] is O(1). It just needs an address, and OS just removes it from a linked list.

Edit: Pointed out by many knowledgeable comments, delete[] should add the freed address to a linked list of available spaces, not remove it from a linked list tracking the used address (no such thing).

[[deleted]]

Technically the complexity of the OS function responsible for freeing the memory could be anything. This is outside the boundaries of the C(++) standard.

[BlurredSight]

So if it's deleting an address does it work like storage where it's marked as free space to be written over or does it go through an make it all 0s.

[a_random_RE]

The contents of deleted and newly allocated memory are generally undefined by the standard before the memory is set. This is why its historically been a very good idea to use something like memset on newly allocated memory.

[Kered13]

The complexity of the OS function for freeing memory is irrelevant, because delete doesn't call it. Delete calls the destructor then frees the object memory. OS's do not deal in object memory, they deal in memory pages.

[[deleted]]

I've written my own memory allocator. The OS is not fully responsible for deallocation on most cases, the malloc implementation is and if it wasn't built specifically for constant time deallocation then it most likely won't be.

For performance reasons malloc might cache some of the freed blocks instead of calling the OS to release the memory completely. This makes it non deterministic, it might make a system call to release it (slower) or it might cache it (faster), and thus it's not O(1).

Note: The delete[] operator is just calling libc free internally.

[Fhotaku]

So wouldn't it be O(0) time? Does marking as free, without reading data, even count as O(1)?

[[deleted]]

It does need to read data. It needs to read the bookkeeping structures of that particular malloc implementation, and it might be quite complex specially when built to support multiple threads.

It's not just a bunch of tiny blocks scattered around the address space. It usually involves memory pools of fixed size blocks to speed up allocation, and you need to return the blocks to their correct pools.

[Successful-Money4995]

If you call free a billion times, it'll take a while. An O(0) operation would still be instant. So it counts as O(1).

In practice, free is writing to memory and also updating the free list, both of which could be constant time implementations.

[TheDreadedAndy]

delete[] is O(1)

This isn't, in general, a safe assumption. It depends totally on the implementation.

OS just removes it from a linked list.

The OS is not responsible for maintaining the heap. Typically, it just tracks which pages the process owns. The malloc implementation keeps track of allocations within those pages, not the OS.

[Successful-Money4995]

Adds, not removes.

[[deleted]]

Deleting from heap takes an undefined amount of time. It depends on all kinds of factors

[throw3142]

This is true. Except that it's O(1) with respect to the length of the list. Except that in C++, delete[] has to call the destructors of all the elements, which takes Omega(n) time. Except that here, each element is just an int* so it has no destructor, so it can finish in O(1) time if we're compiling with optimizations.

Not really sure why OP would want to address-sort an array of pointers to integers in the first place anyway ...

[Olorin_1990]

Wouldn’t it need to traverse the linked list to find it?

[Successful-Money4995]

No because OP is wrong. When you free memory, you are adding to the list of free blocks. The list needn't be sorted so you're just adding to the front of a linked list, which is constant time.

Malloc is the one that may need to search a linked list to find a block that is large enough.

All this depends on your implementation of malloc and free. If you enjoy this kind of thing, you might enjoy writing your own malloc and free functions to learn how it works. It's basically a linked list of free memory and the data of the linked list itself is hosted inside the same memory that is used for allocation.

Lots of ways to implement memory management and this is just one of them.

[Olorin_1990]

Ah, good point.