A RetroSearch Logo

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Search Query:

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/d0/db6/non__recursive__merge__sort_8cpp.html below:

TheAlgorithms/C++: sorting/non_recursive_merge_sort.cpp File Reference

Loading...

Searching...

No Matches

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

Go to the source code of this file.

namespace   sorting   for working with vectors
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 () 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

Copyright 2020

A generic implementation of non-recursive merge sort.

Definition in file non_recursive_merge_sort.cpp.

◆ main()

Definition at line 94 of file non_recursive_merge_sort.cpp.

94 {

95 int size;

96 std::cout << "Enter the number of elements : ";

97 std::cin >> size;

98 int* arr = new int[size];

99 for (int i = 0; i < size; ++i) {

100 std::cout << "arr[" << i << "] = ";

101 std::cin >> arr[i];

102 }

104 std::cout << "Sorted array\n";

105 for (int i = 0; i < size; ++i)

106 std::cout << "arr[" << i << "] = " << arr[i] << '\n';

107 delete[] arr;

108 return 0;

109}

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

◆ 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.

26 {

27

28

29 char* buffer = new char[n * sizeof(*first)];

30

31

32

33 for (size_t length(1); length < n; length <<= 1) {

34

35 Iterator left(first);

36 for (size_t counter(n / (length << 1)); counter; --counter) {

37 Iterator right(left + length), end(right + length);

38 merge

(left, right, end, buffer);

39 left = end;

40 }

41

42

43 if ((n & ((length << 1) - 1)) > length)

44 merge

(left, left + length, last, buffer);

45 }

46 delete[] buffer;

47}

void merge(int *arr, int l, int m, int r)

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4