non_recursive_merge_sort.cpp File Reference

#include <cstddef>
#include <iostream>
#include <utility>

Include dependency graph for non_recursive_merge_sort.cpp:

Go to the source code of this file.

Namespaces
namespace	sorting
	for working with vectors

Functions
template<class Iterator>
void	sorting::merge (Iterator l, Iterator r, const Iterator e, char b[])
	merges 2 sorted adjacent segments into a larger sorted segment
template<class Iterator>
void	sorting::non_recursive_merge_sort (const Iterator first, const Iterator last, const size_t n)
	bottom-up merge sort which sorts elements in a non-decreasing order
template<class Iterator>
void	sorting::non_recursive_merge_sort (const Iterator first, const size_t n)
	bottom-up merge sort which sorts elements in a non-decreasing order
template<class Iterator>
void	sorting::non_recursive_merge_sort (const Iterator first, const Iterator last)
	bottom-up merge sort which sorts elements in a non-decreasing order
int	main (int argc, char **argv)
template<class Iterator>
void	non_recursive_merge_sort (const Iterator first, const Iterator last, const size_t n)
	bottom-up merge sort which sorts elements in a non-decreasing order

Detailed Description

Copyright 2020

Author

Albirair

A generic implementation of non-recursive merge sort.

Definition in file non_recursive_merge_sort.cpp.

Function Documentation

main()

int main	(	int	argc,
		char **	argv )

Definition at line 94 of file non_recursive_merge_sort.cpp.

                                {
    int size;
    std::cout << "Enter the number of elements : ";
    std::cin >> size;
    int* arr = new int[size];
    for (int i = 0; i < size; ++i) {
        std::cout << "arr[" << i << "] = ";
        std::cin >> arr[i];
    }
    non_recursive_merge_sort(arr, size);
    std::cout << "Sorted array\n";
    for (int i = 0; i < size; ++i)
        std::cout << "arr[" << i << "] = " << arr[i] << '\n';
    delete[] arr;
    return 0;
}

non_recursive_merge_sort()

template<class Iterator>

void sorting::non_recursive_merge_sort	(	const Iterator	first,
		const Iterator	last,
		const size_t	n )

bottom-up merge sort which sorts elements in a non-decreasing order

sorts elements non-recursively by breaking them into small segments, merging adjacent segments into larger sorted segments, then increasing the sizes of segments by factors of 2 and repeating the same process. best-case = worst-case = O(n log(n))

Parameters

first	points to the first element
last	points to 1-step past the last element
n	the number of elements

Definition at line 25 of file non_recursive_merge_sort.cpp.

                                              {
    // create a buffer large enough to store all elements
    // dynamically allocated to comply with cpplint
    char* buffer = new char[n * sizeof(*first)];
    // buffer size can be optimized to largest power of 2 less than n
    // elements divide the container into equally-sized segments whose
    // length start at 1 and keeps increasing by factors of 2
    for (size_t length(1); length < n; length <<= 1) {
        // merge adjacent segments whose number is n / (length * 2)
        Iterator left(first);
        for (size_t counter(n / (length << 1)); counter; --counter) {
            Iterator right(left + length), end(right + length);
            merge(left, right, end, buffer);
            left = end;
        }
        // if the number of remaining elements (n * 2 % length) is longer
        // than a segment, merge the remaining elements
        if ((n & ((length << 1) - 1)) > length)
            merge(left, left + length, last, buffer);
    }
    delete[] buffer;
}