15c73097bSWill Gardner/* -*- Mode: C++; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
25c73097bSWill Gardner/*
35c73097bSWill Gardner *     Copyright 2016 Couchbase, Inc
45c73097bSWill Gardner *
55c73097bSWill Gardner *   Licensed under the Apache License, Version 2.0 (the "License");
65c73097bSWill Gardner *   you may not use this file except in compliance with the License.
75c73097bSWill Gardner *   You may obtain a copy of the License at
85c73097bSWill Gardner *
95c73097bSWill Gardner *       http://www.apache.org/licenses/LICENSE-2.0
105c73097bSWill Gardner *
115c73097bSWill Gardner *   Unless required by applicable law or agreed to in writing, software
125c73097bSWill Gardner *   distributed under the License is distributed on an "AS IS" BASIS,
135c73097bSWill Gardner *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
145c73097bSWill Gardner *   See the License for the specific language governing permissions and
155c73097bSWill Gardner *   limitations under the License.
165c73097bSWill Gardner */
175c73097bSWill Gardner
185c73097bSWill Gardner#include <phosphor/phosphor.h>
195c73097bSWill Gardner
205c73097bSWill Gardner/** \file
215c73097bSWill Gardner * This file presents a sample implementation of merge sort that has been
225c73097bSWill Gardner * instrumented with two scoped traces in the merge<T> function and
235c73097bSWill Gardner * merge_sort<T>.
245c73097bSWill Gardner */
255c73097bSWill Gardner
265c73097bSWill Gardnertemplate <class T>
27f99c27afSWill Gardnerstd::vector<T> merge(const std::vector<T>&& left,
28f99c27afSWill Gardner                     const std::vector<T>&& right) {
2926aa9a8bSWill Gardner    TRACE_EVENT2("merge_sort", "merge",
3026aa9a8bSWill Gardner                 "left_size", left.size(),
3126aa9a8bSWill Gardner                 "right_size", right.size());
325c73097bSWill Gardner
335c73097bSWill Gardner    std::vector<T> result;
345c73097bSWill Gardner    auto left_iter = left.begin();
355c73097bSWill Gardner    auto right_iter = right.begin();
365c73097bSWill Gardner
37f99c27afSWill Gardner    while (left_iter != left.end() && right_iter != right.end()) {
385c73097bSWill Gardner        if (*left_iter >= *right_iter) {
395c73097bSWill Gardner            result.push_back(*left_iter);
405c73097bSWill Gardner            left_iter++;
415c73097bSWill Gardner        } else {
425c73097bSWill Gardner            result.push_back(*right_iter);
435c73097bSWill Gardner            right_iter++;
445c73097bSWill Gardner        }
455c73097bSWill Gardner    }
465c73097bSWill Gardner
47f99c27afSWill Gardner    if (left_iter != left.end()) {
485c73097bSWill Gardner        result.insert(result.end(), left_iter, left.end());
495c73097bSWill Gardner    } else {
505c73097bSWill Gardner        result.insert(result.end(), right_iter, right.end());
515c73097bSWill Gardner    }
525c73097bSWill Gardner
535c73097bSWill Gardner    return result;
545c73097bSWill Gardner}
555c73097bSWill Gardner
565c73097bSWill Gardnertemplate <class T>
575c73097bSWill Gardnerstd::vector<T> merge_sort(const std::vector<T>& input) {
5826aa9a8bSWill Gardner    TRACE_EVENT1("merge_sort", "merge_sort", "input_size", input.size());
595c73097bSWill Gardner
605c73097bSWill Gardner    if (input.size() > 1) {
615c73097bSWill Gardner        std::vector<T> left{merge_sort(
62f99c27afSWill Gardner            std::vector<T>(input.begin(), input.begin() + (input.size() / 2)))};
635c73097bSWill Gardner        std::vector<T> right{merge_sort(
64f99c27afSWill Gardner            std::vector<T>(input.begin() + (input.size() / 2), input.end()))};
655c73097bSWill Gardner
665c73097bSWill Gardner        return merge(std::move(left), std::move(right));
675c73097bSWill Gardner
685c73097bSWill Gardner    } else {
695c73097bSWill Gardner        return input;
705c73097bSWill Gardner    }
715c73097bSWill Gardner}
725c73097bSWill Gardner
735c73097bSWill Gardnerint main(int argc, char** argv) {
74f99c27afSWill Gardner    std::vector<int> my_list = {1, 5, 3, 67, 8, 3, 36, 546, 77, 32,
75f99c27afSWill Gardner                                1, 5, 3, 67, 8, 3, 36, 546, 77, 32,
76f99c27afSWill Gardner                                1, 5, 3, 67, 8, 3, 36, 546, 77, 32};
775c73097bSWill Gardner
785c73097bSWill Gardner    std::cout << "Presort: ";
79f99c27afSWill Gardner    for (int num : my_list) {
805c73097bSWill Gardner        std::cout << num << ", ";
815c73097bSWill Gardner    }
825c73097bSWill Gardner    std::cout << "\n\n";
835c73097bSWill Gardner    std::cout << "Post-sort: ";
84f99c27afSWill Gardner    for (int num : merge_sort(my_list)) {
855c73097bSWill Gardner        std::cout << num << ", ";
865c73097bSWill Gardner    }
875c73097bSWill Gardner    std::cout << "\n";
885c73097bSWill Gardner    return 0;
895c73097bSWill Gardner}