This is an attempt to run odd-even sorting from two threads without using locks. I have used a vector and split the vector logically in two halves if the size is beyond a value (Here as an example kept size 10, that means if the vector size is more than 10, then two threads will spawn and parallelize (on multi-core) sorting on the elements of the vector container. Finally, after sorting each half by two threads, another sorting will be arranged to make it finally sorted. The Wiki contains the details about Odd-Even sorting. It's a comparison sorting. The below code snippet is a simple approach to odd-even sorting with multi-threading without having locks. No Extra space was allocated/used in this scenario. void partBySort(std::vector<int>* vec, size_t begIndex, size_t endIndex) { if (begIndex == endIndex) return; bool isSorted = false; while (!isSorted) { isSorted = true; for (size_t i = begIndex; i <= endIndex - 1; i += 2) {